Submission #4272156
Source Code Expand
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define fi first #define se second #define mp make_pair #define pb push_back typedef long long ll; typedef pair<ll,ll> ii; typedef vector<ll> vi; typedef unsigned long long ull; typedef long double ld; typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds; bool cmp(const ii &a, const ii &b) { ll lena = a.se-a.fi; ll lenb = b.se-b.fi; if(lena!=lenb) return lena>lenb; else return a.fi<a.se; } ll pref[5011][5011]; ll suf[2][5011]; void amin(ll &a, ll b) { a=min(a,b); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin>>n; vector<ii> vec; for(int i=0;i<n;i++) { ll l,r; cin>>l>>r; vec.pb({-l,r}); } sort(vec.begin(),vec.end(),cmp); /* for(int i=0;i<n;i++) { cerr<<vec[i].fi<<' '<<vec[i].se<<'\n'; } */ ll ans = ll(2e18); for(int l=(n-1)/2;l<=n/2;l++) { int r=n-1-l; for(int i=0;i<n;i++) { for(int j=0;j<=n;j++) { pref[i][j]=ll(1e18); } } for(int i=0;i<2;i++) { for(int j=0;j<=n;j++) { suf[i][j]=ll(1e18); } } pref[0][0]=vec[0].se; pref[0][1]=-vec[0].fi; for(int i=0;i+1<n;i++) { for(int j=0;j<=n;j++) { if(pref[i][j]<ll(1e18)) { ll v=pref[i][j]; ll L=vec[i+1].fi; ll R=vec[i+1].se; //go left amin(pref[i+1][j], v+R+ll(i+1-j)*(R-L)); //go right amin(pref[i+1][j+1], v-L+ll(j)*(R-L)); } } } suf[(n-1)&1][0]=vec[n-1].se+ll(l-1)*(vec[n-1].se-vec[n-1].fi); suf[(n-1)&1][1]=-vec[n-1].fi+ll(r-1)*(vec[n-1].se-vec[n-1].fi); for(int i=max(n-2,0);i<n;i++) { //segment i is fixed ll constant = vec[i].se*r-vec[i].fi*l; for(int j=0;j<=r;j++) { ll lef = 0; ll ri = 0; if(i==0) { if(j!=0) lef=ll(1e18); } else lef=pref[i-1][j]; if(i==n-1) { if(r-j!=0) ri=ll(1e18); } else ri=suf[(i+1)&1][r-j]; //cerr<<i<<' '<<j<<' '<<constant<<' '<<lef<<' '<<ri<<'\n'; ans = min(ans, constant+lef+ri); } } for(int i=n-1;i>0;i--) { int cur=(i+1)&1; int pre=cur^1; for(int j=0;j<=n;j++) suf[cur][j]=ll(1e18); for(int j=0;j<=n;j++) { if(suf[pre][j]<ll(1e18)) { ll v=suf[pre][j]; ll L=vec[i-1].fi; ll R=vec[i-1].se; //go left amin(suf[cur][j], v+R+ll(l-1-((n-1-i)+1-j))*(R-L)); //go right amin(suf[cur][j+1], v-L+ll(r-1-j)*(R-L)); } } { int i2=i-2; if(i2<0) continue; ll constant = vec[i2].se*r-vec[i2].fi*l; for(int j=0;j<=r;j++) { ll lef = 0; ll ri = 0; if(i2==0) { if(j!=0) lef=ll(1e18); } else lef=pref[i2-1][j]; if(i2==n-1) { if(r-j!=0) ri=ll(1e18); } else ri=suf[cur][r-j]; //cerr<<i<<' '<<j<<' '<<constant<<' '<<lef<<' '<<ri<<'\n'; ans = min(ans, constant+lef+ri); } } } } cout<<ans<<'\n'; }
Submission Info
Submission Time | |
---|---|
Task | F - Intervals |
User | zscoder |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 3115 Byte |
Status | RE |
Exec Time | 342 ms |
Memory | 196352 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1000 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0.txt, example1.txt |
All | 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, example0.txt, example1.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
000.txt | AC | 338 ms | 196352 KB |
001.txt | AC | 72 ms | 83328 KB |
002.txt | AC | 338 ms | 196352 KB |
003.txt | AC | 145 ms | 170368 KB |
004.txt | AC | 338 ms | 196352 KB |
005.txt | AC | 81 ms | 120576 KB |
006.txt | AC | 339 ms | 196272 KB |
007.txt | AC | 172 ms | 137216 KB |
008.txt | AC | 338 ms | 196352 KB |
009.txt | AC | 39 ms | 58496 KB |
010.txt | AC | 338 ms | 196272 KB |
011.txt | AC | 150 ms | 126848 KB |
012.txt | AC | 338 ms | 196352 KB |
013.txt | AC | 33 ms | 52224 KB |
014.txt | AC | 338 ms | 196352 KB |
015.txt | AC | 45 ms | 83328 KB |
016.txt | AC | 338 ms | 196272 KB |
017.txt | AC | 256 ms | 170368 KB |
018.txt | AC | 338 ms | 196352 KB |
019.txt | AC | 96 ms | 132992 KB |
020.txt | AC | 1 ms | 256 KB |
021.txt | AC | 1 ms | 256 KB |
022.txt | RE | 100 ms | 512 KB |
023.txt | AC | 338 ms | 196352 KB |
024.txt | AC | 339 ms | 196272 KB |
025.txt | AC | 339 ms | 196272 KB |
026.txt | AC | 339 ms | 196352 KB |
027.txt | AC | 338 ms | 196352 KB |
028.txt | AC | 338 ms | 196272 KB |
029.txt | AC | 339 ms | 196272 KB |
030.txt | AC | 339 ms | 196272 KB |
031.txt | AC | 339 ms | 196272 KB |
032.txt | AC | 338 ms | 196352 KB |
033.txt | AC | 338 ms | 196352 KB |
034.txt | AC | 338 ms | 196272 KB |
035.txt | AC | 339 ms | 196352 KB |
036.txt | AC | 338 ms | 196352 KB |
037.txt | AC | 338 ms | 196352 KB |
038.txt | AC | 339 ms | 196352 KB |
039.txt | AC | 338 ms | 196272 KB |
040.txt | AC | 342 ms | 196272 KB |
041.txt | AC | 340 ms | 196272 KB |
042.txt | AC | 339 ms | 196352 KB |
example0.txt | AC | 1 ms | 256 KB |
example1.txt | AC | 1 ms | 384 KB |