結果
問題 | No.2546 Many Arithmetic Sequences |
ユーザー | maksim |
提出日時 | 2023-11-24 21:42:09 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 380 ms / 2,000 ms |
コード長 | 2,738 bytes |
コンパイル時間 | 2,396 ms |
コンパイル使用メモリ | 189,668 KB |
実行使用メモリ | 39,712 KB |
最終ジャッジ日時 | 2023-11-25 20:44:54 |
合計ジャッジ時間 | 10,866 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,548 KB |
testcase_01 | AC | 2 ms
6,548 KB |
testcase_02 | AC | 2 ms
6,548 KB |
testcase_03 | AC | 110 ms
16,744 KB |
testcase_04 | AC | 195 ms
19,312 KB |
testcase_05 | AC | 155 ms
15,104 KB |
testcase_06 | AC | 32 ms
6,584 KB |
testcase_07 | AC | 71 ms
10,132 KB |
testcase_08 | AC | 20 ms
6,548 KB |
testcase_09 | AC | 74 ms
12,736 KB |
testcase_10 | AC | 140 ms
18,976 KB |
testcase_11 | AC | 161 ms
25,248 KB |
testcase_12 | AC | 54 ms
10,376 KB |
testcase_13 | AC | 169 ms
17,100 KB |
testcase_14 | AC | 183 ms
22,244 KB |
testcase_15 | AC | 43 ms
8,732 KB |
testcase_16 | AC | 169 ms
19,680 KB |
testcase_17 | AC | 259 ms
19,064 KB |
testcase_18 | AC | 146 ms
14,284 KB |
testcase_19 | AC | 131 ms
14,548 KB |
testcase_20 | AC | 81 ms
11,980 KB |
testcase_21 | AC | 59 ms
10,836 KB |
testcase_22 | AC | 163 ms
16,600 KB |
testcase_23 | AC | 380 ms
33,392 KB |
testcase_24 | AC | 371 ms
33,428 KB |
testcase_25 | AC | 363 ms
33,392 KB |
testcase_26 | AC | 361 ms
33,444 KB |
testcase_27 | AC | 378 ms
33,412 KB |
testcase_28 | AC | 310 ms
39,712 KB |
testcase_29 | AC | 305 ms
39,712 KB |
testcase_30 | AC | 304 ms
39,712 KB |
testcase_31 | AC | 310 ms
39,712 KB |
testcase_32 | AC | 300 ms
39,712 KB |
testcase_33 | AC | 2 ms
6,548 KB |
testcase_34 | AC | 273 ms
30,148 KB |
testcase_35 | AC | 2 ms
6,548 KB |
testcase_36 | AC | 299 ms
32,208 KB |
testcase_37 | AC | 2 ms
6,548 KB |
testcase_38 | AC | 1 ms
6,548 KB |
コンパイルメッセージ
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(-1e18); 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((i!=0)*(-1e18)); return answ;} vector<pair<int,int> > l; for(auto [a,d]:v) { l.push_back({-d,-2*a+d}); } sort(l.begin(),l.end());reverse(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;assert(ans%2==0);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=(-1e18); for(int i=0;i<=m;++i) {answ=max(answ,res1[i]+res2[m-i]);} cout<<answ; return 0; }