Submission #1300064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300064		loom	Bring Down the Grading Server (CEOI23_gradingserver)	C++20	10 / 100	1522 ms	214920 KiB

gradingserver

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)2e18
#define nl '\n'

const int N = 301;
int dp[N][N][N];

void solve(){
   int s, q;
   cin>>s>>q;

   for(int c1 = 0; c1 < N; c1++){
      for(int c2 = 0; c2 < N; c2++){
         for(int f2 = 0; f2 < N; f2++){
            int &x = dp[c1][c2][f2];

            if(c1 == 0){
               x = N;
               continue;
            }
            if(c2 == 0){
               x = 0;
               continue;
            }

            int l = 0, r = N;
            while(l < r){
               int f1 = (l+r)/2;

               int ff = (f2 > 0 and dp[c1][c2][f2-1] <= max(0ll, f1-1));
               int fa = (f2 > 0 and dp[max(0ll, c1 - max(0ll, c2 - s*f1))][c2][f2-1] <= f1);
               int af = 0, aa = 0;
               
               int p = c1 - s*f2;
               if(p > 0){
                  af = (dp[c1][max(0ll, c2 - p)][f2] <= max(0ll, f1-1));
                  aa = (dp[max(0ll, c1 - max(0ll, c2 - p - s*f1))][max(0ll, c2 - p)][f2] <= f1);
               }

               if(ff and fa or c2 - p <= 0 or af and aa) r = f1;
               else l = f1+1;
            }

            x = l;
         }
      }
   }

   while(q--){
      int c1, f1, c2, f2;
      cin>>c1>>f1>>c2>>f2;

      cout<<(dp[c1][c2][f2] <= f1 ? "YES" : "NO")<<nl;
   }
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 10
• Subtask 5: 0 / 25
• Subtask 4: 0 / 20
• Subtask 6: 0 / 20
• Subtask 7: 0 / 15