結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2017-02-25 00:05:15 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 117 ms / 1,000 ms |
コード長 | 1,207 bytes |
コンパイル時間 | 690 ms |
コンパイル使用メモリ | 76,844 KB |
実行使用メモリ | 8,192 KB |
最終ジャッジ日時 | 2024-07-19 23:13:08 |
合計ジャッジ時間 | 2,790 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <string>#include <map>using namespace std;#define rep(i,n) for(int i=0;i<n;i++)int main(){long long n, d, k; cin >> n >> d >> k;vector<int>x(n);for (int i = 0; i < n; i++) {cin >> x[i];}map<int,int>m;pair<int,int> ans = make_pair(0,0);for (int i = 0; i <= d;i++) {if (m.find(x[i]) == m.end()) {m[x[i]] = 1;}else m[x[i]]++;}auto fin = --m.end();ans = make_pair(fin->first - x[0], 0);for (int i = d + 1; i < n; i++) {m[x[i - d - 1]]--;if (m[x[i - d - 1]] == 0)m.erase(m.find(x[i - d - 1]));m[x[i]]++;auto fin = --m.end();if (ans.first < fin->first - x[i - d]) {ans = make_pair(fin->first - x[i - d], i - d);}}for (int i = n - d - 1; i < n-1; i++) {m[x[i]]--;if (m[x[i]] == 0)m.erase(m.find(x[i]));auto fin = --m.end();if (ans.first < fin->first - x[i+1]) {ans = make_pair(fin->first - x[i+1], i+1);}}cout << (long long)ans.first*k << endl;if (ans.first) {for (int i = ans.second; i <= min(n-1,ans.second + d); i++) {if (x[i] - x[ans.second] == ans.first) {cout << ans.second << " " << i << endl;break;}}}return 0;}