結果
問題 | No.2546 Many Arithmetic Sequences |
ユーザー | maksim |
提出日時 | 2023-11-24 21:38:36 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,671 bytes |
コンパイル時間 | 2,230 ms |
コンパイル使用メモリ | 188,860 KB |
実行使用メモリ | 40,100 KB |
最終ジャッジ日時 | 2024-09-26 09:55:38 |
合計ジャッジ時間 | 10,585 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | WA | - |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 142 ms
18,964 KB |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | AC | 182 ms
22,540 KB |
testcase_15 | AC | 42 ms
8,612 KB |
testcase_16 | AC | 167 ms
19,560 KB |
testcase_17 | WA | - |
testcase_18 | AC | 129 ms
14,160 KB |
testcase_19 | WA | - |
testcase_20 | AC | 86 ms
11,980 KB |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | AC | 319 ms
39,596 KB |
testcase_30 | AC | 327 ms
39,420 KB |
testcase_31 | WA | - |
testcase_32 | AC | 338 ms
38,908 KB |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | AC | 2 ms
6,940 KB |
testcase_36 | AC | 294 ms
32,212 KB |
testcase_37 | AC | 2 ms
6,944 KB |
testcase_38 | WA | - |
コンパイルメッセージ
main.cpp: In function 'std::vector<long long int> slv2(std::vector<std::pair<long long int, long long int> >, long long int)': main.cpp:70:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 70 | for(auto [a,d]:v) | ^ main.cpp:75:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 75 | for(auto [k,b]:l) | ^
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long #define app push_back #ifndef LOCAL #define endl '\n' #endif // LOCAL typedef long long ll; struct Line { ll k, b; Line() : k(), b() {} Line (ll _k, ll _b) : k(_k), b(_b) {} ll getVal(ll x) { return k * x + b; } }; ll div_up(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up struct Hull { vector<Line> lines; vector<ll> borders; Hull() : lines(), borders() {} void addLine(Line L) { while(!lines.empty()) { if (lines.back().getVal(borders.back()) >= L.getVal(borders.back())) { lines.pop_back(); borders.pop_back(); } else break; } if (lines.empty()) { lines.push_back(L); borders.push_back(0LL); //leftmost query return; } if (lines.back().k <= L.k) return; ll x = div_up(L.b - lines.back().b, lines.back().k - L.k); //must work for negative! lines.push_back(L); borders.push_back(x); } ll getMinVal(ll x) { int pos = upper_bound(borders.begin(), borders.end(), x) - borders.begin(); if (pos == 0) throw; pos--; return lines[pos].getVal(x); } }; Hull c; vector<int> slv1(vector<pair<int,int> > a,int m) { set<pair<int,int> > d; vector<int> answ={0}; if(a.empty()) {for(int i=0;i<m;++i) answ.push_back(0); return answ;} for(int i=0;i<a.size();++i) {d.insert({a[i].first,i});} for(int i=0;i<m;++i) { auto o=*--d.end();d.erase(o); answ.push_back(answ.back()+o.first); o.first+=a[o.second].second;d.insert(o); } return answ; } vector<int> slv2(vector<pair<int,int> > v,int m) { if(v.empty()) {vector<int> answ;for(int i=0;i<=m;++i) answ.push_back(0); return answ;} vector<pair<int,int> > l; for(auto [a,d]:v) { l.push_back({-d,-2*a+d}); } sort(l.begin(),l.end()); for(auto [k,b]:l) { c.addLine(Line(k,b)); } vector<int> res; for(int i=0;i<=m;++i) { int ans=-c.getMinVal(i); ans*=i;ans/=2; res.push_back(ans); } return res; } int32_t main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n,m;cin>>n>>m; vector<pair<int,int> > v1,v2; for(int i=0;i<n;++i) {int x,y;cin>>x>>y;if(y<=0) {v1.push_back({x,y});} else {v2.push_back({x,y});}} vector<int> res1=slv1(v1,m);vector<int> res2=slv2(v2,m); //for(int x:res1) cout<<x<<' '; cout<<endl; int answ=0; for(int i=0;i<=m;++i) {answ=max(answ,res1[i]+res2[m-i]);} cout<<answ; return 0; }