Submission #987338

#	Time	Username	Problem	Language	Result	Execution time	Memory
987338		AdamGS	Packing Biscuits (IOI20_biscuits)	C++17	9 / 100	1099 ms	843904 KiB

biscuits

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "biscuits.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
vector<ll>V[65], dp[65];
vector<ll>merge(vector<ll>A, vector<ll>B) {
  ll l=0;
  vector<ll>ans;
  for(auto i : A) {
    while(l<B.size() && B[l]<i) {
      ans.pb(B[l]);
      ++l;
    }
    ans.pb(i);
  }
  while(l<B.size()) {
    ans.pb(B[l]);
    ++l;
  }
  return ans;
}
ll count_tastiness(ll x, vector<ll>T) {
  ll n=T.size();
  T.pb(0);
  rep(i, n+1) {
    V[i].clear();
    dp[i].clear();
  }
  V[0].pb(0);
  rep(i, n) {
    rep(j, V[i].size()) V[i][j]+=T[i];
    vector<ll>A, B;
    rep(j, V[i].size()) A.pb(V[i][j]/2);
    rep(j, V[i].size()) if(V[i][j]>=x) B.pb((V[i][j]-x)/2);
    V[i+1]=merge(A, B);
  }
  rep(i, V[n].size()) dp[n].pb(V[n][i]/x+1);
  rep(i, n) dp[i].resize(V[i].size());
  for(int i=n-1; i>=0; --i) {
    int l=0;
    rep(j, V[i].size()) {
      while(V[i+1][l]<V[i][j]/2+T[i+1]) ++l;
      dp[i][j]=dp[i+1][l];
    }
    l=0;
    rep(j, V[i].size()) if(V[i][j]>=x) {
      while(V[i+1][l]<(V[i][j]-x)/2+T[i+1]) ++l;
      dp[i][j]+=dp[i+1][l];
    }
  }
  return dp[0][0];
}

Compilation message (stderr)

biscuits.cpp: In function 'std::vector<long long int> merge(std::vector<long long int>, std::vector<long long int>)':
biscuits.cpp:17:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     while(l<B.size() && B[l]<i) {
      |           ~^~~~~~~~~
biscuits.cpp:23:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   while(l<B.size()) {
      |         ~^~~~~~~~~
biscuits.cpp: In function 'll count_tastiness(ll, std::vector<long long int>)':
biscuits.cpp:7:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
biscuits.cpp:38:5: note: in expansion of macro 'rep'
   38 |     rep(j, V[i].size()) V[i][j]+=T[i];
      |     ^~~
biscuits.cpp:7:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
biscuits.cpp:40:5: note: in expansion of macro 'rep'
   40 |     rep(j, V[i].size()) A.pb(V[i][j]/2);
      |     ^~~
biscuits.cpp:7:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
biscuits.cpp:41:5: note: in expansion of macro 'rep'
   41 |     rep(j, V[i].size()) if(V[i][j]>=x) B.pb((V[i][j]-x)/2);
      |     ^~~
biscuits.cpp:7:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
biscuits.cpp:44:3: note: in expansion of macro 'rep'
   44 |   rep(i, V[n].size()) dp[n].pb(V[n][i]/x+1);
      |   ^~~
biscuits.cpp:7:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
biscuits.cpp:48:5: note: in expansion of macro 'rep'
   48 |     rep(j, V[i].size()) {
      |     ^~~
biscuits.cpp:7:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
biscuits.cpp:53:5: note: in expansion of macro 'rep'
   53 |     rep(j, V[i].size()) if(V[i][j]>=x) {
      |     ^~~

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 21
• Subtask 4: 0 / 35
• Subtask 5: 0 / 23