結果
問題 |
No.2546 Many Arithmetic Sequences
|
ユーザー |
|
提出日時 | 2023-12-08 22:40:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,351 bytes |
コンパイル時間 | 2,472 ms |
コンパイル使用メモリ | 202,444 KB |
最終ジャッジ日時 | 2025-02-18 09:39:10 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 WA * 5 RE * 1 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(0); ll N, M; cin >> N >> M; auto sum = [&](ll a, ll d) { return (a + a + (M - 1) * d) * M / 2; }; vector<ll> A(N), D(N); for(ll i = 0; i < N; i++) { cin >> A[i] >> D[i]; } ll m = 0, idx = -1; for(ll i = 0; i < N; i++) { if(D[i] < 0) { continue; } ll tmp = sum(A[i], D[i]); if(tmp > m) { idx = i; m = tmp; } else if(tmp == m) { if(idx == -1 || D[idx] > D[i]) { idx = i; } } } if(idx == -1) { priority_queue<pair<ll, ll>> q; for(ll i = 0; i < N; i++) { q.emplace(A[i], D[i]); } ll ans = 0; for(ll i = 0; i < M; i++) { auto [t, d] = q.top(); q.pop(); ans += t; q.emplace(t + d, d); } cout << ans << "\n"; } else { vector<ll> single; for(ll i = 0; i < M; i++) { single.emplace_back(A[idx] + D[idx] * i); } priority_queue<pair<ll, ll>> q; for(ll i = 0; i < N; i++) { if(D[i] < 0) { q.emplace(A[i], D[i]); } } ll ans = m; for(ll i = 0; i < M; i++) { auto [t, d] = q.top(); q.pop(); if(t > single.back()) { ans += t - single.back(); single.pop_back(); q.emplace(t + d, d); } else { break; } } cout << ans << "\n"; } }