Submission #1238769

#TimeUsernameProblemLanguageResultExecution timeMemory
1238769modwwePinball (JOI14_pinball)C++17
Compilation error
0 ms0 KiB
//#pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> //#define int long long #define ll long long #define down cout<<'\n'; #define debug cout<<" cucuucucuuu",down #define modwwe int t;cin>>t; while(t--) #define bit(i,j) (i>>j&1) #define sobit(a) __builtin_popcountll(a) #define task2 "top1apio" #define task "test" #define fin(x) freopen(x".inp","r",stdin) #define fou(x) freopen(x".out","w",stdout) #define pb push_back #define mask(k) (1ll<<k) #define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms"; using namespace std; #define getchar_unlocked getchar mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); using i128 = __int128; int rand(int l, int r) { return uniform_int_distribution<int>(l, r)(rd); } void phongbeo(); const int inf = 1e9; const int mod2 = 1e9 + 7; //const ll base=67; int n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center; int i, s10, s12, k1, k2, k3, s11, lim, w, l, r, dem5, dem6, dem7, dem9, now, root, q, en; int el = 19; main() { ///top1apio if (fopen(task2".inp", "r")) { fin(task2); fou(task2); } ///top1apio if (fopen(task".inp", "r")) { fin(task); fou(task); } ///top1apio ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); // cin>>s1; //9 ll t;cin>>t;while(t--) phongbeo(); /// checktime ///top1apio } int dp[2007][2007],d[2007][2007],c[2007][2007]; struct ib{int a,b;} ib a[2007]; int nxt[2007]; bool cmp(ib a,ib b) { return a.b<b.b; } void go(int x,int y,int val,int mx) { if(dem>k)return; if(x==0&&d[1][s2]<=mx) { dem++; } else return; if(y==s2)return; bool ok=0; for(int i=x+1; i<=n; i++) { if(d[i][y+1]+val>mx)break; if(a[i].b>=y+1&&c[i][y+1]+val<=mx) { dem+=ok; ok=1; go(i,y+1,val+a[i].a,mx); } if(dem>k)return; } } void work(int x,int y,int val,int hihi,int mx) { if(y==hihi) { v.pb({y,mx}); return; } if(hihi==s2) { for(int i=x+1; i<=n; i++) if(a[i].b>=y+1&&c[i][y+1]+val<=mx) work(i,y+1,val+a[i].a,hihi,mx); } else { for(int i=x+1;i<=n;i++) if(a[i].b>=y+1&&dp[i][y+1]+y+1>=hihi) work(i,y+1,0,hihi,0); } } bool check(int x) { dem=0; go(0,0,0,x); if(dem>k)return 1; return 0; } void phongbeo() { cin>>n>>k; for(int i=1; i<=n; i++) cin>>a[i].a>>a[i].b; sort(a+1,a+1+n,cmp); for(int i=1; i<=n+1; i++) nxt[i]=n+1; for(int i=n; i>=1; --i) nxt[a[i].b]=i; for(int i=n; i>=1; --i) if(nxt[i]==n+1)nxt[i]=nxt[i+1]; dp[1][1]=1; for(int i=1; i<n; i++) for(int j=1; j<=i; j++) { s3=nxt[j+1]; if(s3>i)dp[s3][j+1]+=dp[i][j]; else dp[i+1][j+1]+=dp[i][j]; dp[i+1][j]+=dp[i][j]; } for(int i=2; i<=n; i++) for(int j=1; j<=i-1; j++) dp[i][j]+=dp[i][j-1]; for(int i=n; i>=1; --i) { if(dp[n][i]<=k) { k-=dp[n][i]; } else { s2=i; break; } } memset(dp,0,sizeof dp); for(int i=n; i>=2; --i) for(int j=2; j<=a[i].b; j++) { s3=nxt[j-1]; dp[i-1][j-1]=dp[i][j]+1; } for(int i=1; i<=n; i++) if(a[i].b<=s2) c[i][s2]=a[i].a; for(int i=1; i<=n; i++) for(int j=1; j<=s2; j++) c[i][j]=inf; for(int i=1; j<=s2; j++) d[n][i]=c[n][i]; for(int i=n-1; i>=1; --i) for(int j=1; j<=s2; j++) { s3=nxt[j+1]; if(s3==n+1)continue; if(j<=a[i].b) { if(s3>i)c[i][j]=min(c[i][j],d[s3][j+1]+a[i].a); else c[i][j]=min(c[i][j],d[i+1][j+1]+a[i].a); } d[i][j]=min(d[i+1][j],c[i][j]); } if(k==0)r=-1; l=0; r=s2*1e9-1; while(l<=r) { int mid=l+r>>1; if(check(mid))r=mid-1; else l=mid+1; } work(0,0,0,s2+1,0); work(0,0,0,s2,r); }

Compilation message (stderr)

pinball.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main()
      | ^~~~
pinball.cpp:61:4: error: expected initializer before 'a'
   61 | ib a[2007];
      |    ^
pinball.cpp: In function 'void go(int, int, int, int)':
pinball.cpp:80:12: error: 'a' was not declared in this scope
   80 |         if(a[i].b>=y+1&&c[i][y+1]+val<=mx)
      |            ^
pinball.cpp: In function 'void work(int, int, int, int, int)':
pinball.cpp:93:9: error: 'v' was not declared in this scope
   93 |         v.pb({y,mx});
      |         ^
pinball.cpp:99:12: error: 'a' was not declared in this scope
   99 |         if(a[i].b>=y+1&&c[i][y+1]+val<=mx)
      |            ^
pinball.cpp:105:12: error: 'a' was not declared in this scope
  105 |         if(a[i].b>=y+1&&dp[i][y+1]+y+1>=hihi)
      |            ^
pinball.cpp: In function 'void phongbeo()':
pinball.cpp:120:14: error: 'a' was not declared in this scope
  120 |         cin>>a[i].a>>a[i].b;
      |              ^
pinball.cpp:121:10: error: 'a' was not declared in this scope
  121 |     sort(a+1,a+1+n,cmp);
      |          ^
pinball.cpp:165:18: error: 'j' was not declared in this scope
  165 |     for(int i=1; j<=s2; j++)
      |                  ^
pinball.cpp: In function 'int main()':
pinball.cpp:12:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
pinball.cpp:38:9: note: in expansion of macro 'fin'
   38 |         fin(task2);
      |         ^~~
pinball.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
pinball.cpp:39:9: note: in expansion of macro 'fou'
   39 |         fou(task2);
      |         ^~~
pinball.cpp:12:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
pinball.cpp:45:9: note: in expansion of macro 'fin'
   45 |         fin(task);
      |         ^~~
pinball.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
pinball.cpp:46:9: note: in expansion of macro 'fou'
   46 |         fou(task);
      |         ^~~