結果
問題 | No.59 鉄道の旅 |
ユーザー |
![]() |
提出日時 | 2014-11-06 23:48:27 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2,270 ms / 5,000 ms |
コード長 | 719 bytes |
コンパイル時間 | 1,282 ms |
コンパイル使用メモリ | 161,276 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-12-24 20:01:14 |
合計ジャッジ時間 | 6,372 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 12 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:14:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 14 | scanf("%d", w+i); | ~~~~~^~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>using namespace std;#define REP(i,n) for(int i=0;i<(int)(n);++i)int w[1000000];int a[1000000];int c[1000000];int main() {int n,k;while(scanf("%d%d",&n,&k) == 2) {REP(i,n) {c[i] = 0;scanf("%d", w+i);a[i] = abs(w[i]);}sort(a,a+n);int m = unique(a,a+n) - a;REP(i,n) {if (w[i]>0) {int id = lower_bound(a,a+m,w[i]) - a;int sm = 0;for (int j=id; j<m; ++j) sm += c[j];if (sm < k) c[id]++;} else {int id = lower_bound(a,a+m,-w[i]) - a;if (c[id]) c[id]--;}}int ans = 0;REP(i,n) ans+=c[i];cout << ans << endl;}}