oj.uz

Submission #601051

# Submission time Handle Problem Language Result Execution time Memory
601051 2022-07-21T10:36:59 Z MohammadAghil Kitchen (BOI19_kitchen) C++17
100 / 100
 685 ms 91260 KB 
      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
    #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
      #define per(i,r,l) for(int i = (r); i >= (l); i--)
        #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) begin(x), end(x)
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     // #ifndef ONLINE_JUDGE
     //      freopen("in.in", "r", stdin);
     //      freopen("out.out", "w", stdout);
     // #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 300 + 5, lg = 22, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
 
int a[maxn], b[maxn], dp[maxn][maxn*maxn], nxt[maxn*maxn];
bitset<maxn*maxn> can;
 
int main(){ IOS();
     int n, m, k; cin >> n >> m >> k;
     rep(i,0,n) cin >> a[i];    
     rep(i,0,m) cin >> b[i];    
     
     rep(i,0,n) if(a[i] < k) return cout << "Impossible\n", 0;
 
     int s = 0;
     rep(i,0,n) s += a[i];
 
     vector<int> c;
     can[0] = true;
     rep(i,0,m) {
          if(b[i] >= n) c.pb(b[i]);
          else can |= can<<b[i];
     }

     er(sz(c));

     int lst = -1;
     per(i,maxn*maxn-1,0){
          if(can[i]) lst = i, er(i);
          nxt[i] = lst;
     }
     

     rep(i,0,sz(c)) rep(j,0,maxn*maxn){
          if(!i){
               if(c[i] == j) dp[i][j] = 1;
               continue;
          }
          dp[i][j] = dp[i-1][j];
          if(j == c[i]) dp[i][j] = max(dp[i][j], 1);
          else if(j > c[i] && dp[i-1][j-c[i]]) dp[i][j] = max(dp[i][j], dp[i-1][j-c[i]]+1);
     }
 
     rep(i,0,10) er(i, dp[sz(c)-1][i]);
 
     int ans = inf;
     rep(s1,0,maxn*maxn){
          if(!s1 || (sz(c) && dp[sz(c)-1][s1])){
               int v1 = n*(k-(s1?dp[sz(c)-1][s1]:0));
               int v2 = s - s1;
               int mx = max({v1, v2, 0});
               if(nxt[mx] + 1) ans = min(ans, s1 + nxt[mx]);
          }
     }
 
     if(ans == inf) cout << "Impossible\n";
     else cout << ans - s << '\n';
     return 0; 
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Correct 1 ms 732 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 980 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Correct 1 ms 732 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 6 ms 5712 KB Output is correct
10 Correct 6 ms 5716 KB Output is correct
11 Correct 5 ms 4308 KB Output is correct
12 Correct 3 ms 736 KB Output is correct
13 Correct 28 ms 1748 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 12888 KB Output is correct
2 Correct 311 ms 14408 KB Output is correct
3 Correct 436 ms 21564 KB Output is correct
4 Correct 510 ms 60184 KB Output is correct
5 Correct 685 ms 38876 KB Output is correct
6 Correct 196 ms 9556 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 13468 KB Output is correct
2 Correct 11 ms 7328 KB Output is correct
3 Correct 11 ms 2132 KB Output is correct
4 Correct 12 ms 2900 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Correct 1 ms 732 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 6 ms 5712 KB Output is correct
10 Correct 6 ms 5716 KB Output is correct
11 Correct 5 ms 4308 KB Output is correct
12 Correct 3 ms 736 KB Output is correct
13 Correct 28 ms 1748 KB Output is correct
14 Correct 299 ms 12888 KB Output is correct
15 Correct 311 ms 14408 KB Output is correct
16 Correct 436 ms 21564 KB Output is correct
17 Correct 510 ms 60184 KB Output is correct
18 Correct 685 ms 38876 KB Output is correct
19 Correct 196 ms 9556 KB Output is correct
20 Correct 12 ms 13468 KB Output is correct
21 Correct 11 ms 7328 KB Output is correct
22 Correct 11 ms 2132 KB Output is correct
23 Correct 12 ms 2900 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 62 ms 73436 KB Output is correct
26 Correct 71 ms 86216 KB Output is correct
27 Correct 90 ms 36580 KB Output is correct
28 Correct 203 ms 56300 KB Output is correct
29 Correct 76 ms 91260 KB Output is correct
30 Correct 365 ms 69296 KB Output is correct