Submission #16514414


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <queue>
typedef long long ll;
#define rep(i,n) for(int i = 0;i<n;++i)
#define repc(bit,k,n) for (int bit = (1<<k)-1;bit < (1<<n); bit = next_combination(bit))
#define repi(itr,vec) for(auto itr = vec.begin();itr!=vec.end();++itr)
using namespace std;
using Graph = vector<vector<int> >;

/* next combination
 * usage:repc(bit,k,n)
 * */
inline int next_combination(int sub) {
  int x = sub & -sub, y = sub + x;
  return (((sub & ~y) / x) >> 1) | y;
}

/* uniq
 * usage:uniq(vec)
 * */
void uniq(vector<int> &vec){
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  return;
}

/* BinaryIndexedTree
 * usage:update and sum of 1~N
 * */
int N;
int bit[1000010];
void add(int a, int w) {
  for (int x = a; x <= N; x += x & -x) bit[x] += w;
}
int sum(int a) {
  int ret = 0;
  for (int x = a; x > 0; x -= x & -x) ret += bit[x];
  return ret;
}

/* DP
 * usage: chmin(dp[i],dp[i-1]+v);
 * */
const ll INF = 1LL << 60;
ll dp[101][101][101];

template<class T> inline bool chmin(T& a, T b) {
      if (a > b) {
                a = b;
                        return true;
                            }
          return false;
}
template<class T> inline bool chmax(T& a, T b) {
      if (a < b) {
                a = b;
                        return true;
                            }
          return false;
}

int count16bit(unsigned short v) {
  unsigned short count = (v & 0x5555) + ((v >> 1) & 0x5555);
  count = (count & 0x3333) + ((count >> 2) & 0x3333);
  count = (count & 0x0f0f) + ((count >> 4) & 0x0f0f);
  return (count & 0x00ff) + ((count >> 8) & 0x00ff);
}
ll solve(ll a,ll b, ll c, const vector<vector<ll> > &company){
  repi(itr,company){
    if(((*itr)[1]<=a)&&((*itr)[2]<=b)&&((*itr)[3]<=c))return (*itr)[0];
  }
  return 0;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,m;cin>>n>>m;
  fill((ll*)dp, (ll*)dp+ sizeof(dp)/sizeof(ll),0);
  rep(i,n){
    int a,b,c;cin>>a>>b>>c;
    ll w;cin>>w;
    chmax(dp[a][b][c],w);
  }
  rep(i,101){
    rep(j,101){
      rep(k,101){
        chmax(dp[i][j][k],dp[(i-1)>=0?i-1:0][j][k]);
        chmax(dp[i][j][k],dp[i][(j-1)>=0?j-1:0][k]);
        chmax(dp[i][j][k],dp[i][j][(k-1)>=0?k-1:0]);
      }
    }

  }
  rep(i,m){
    int a,b,c;cin>>a>>b>>c;
    cout<<dp[a][b][c]<<endl;
  }


  return 0;
}

Submission Info

Submission Time
Task C - Optimal Recommendations
User koppepyan
Language C++ (GCC 9.2.1)
Score 100
Code Size 2519 Byte
Status AC
Exec Time 115 ms
Memory 11560 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 24
Set Name Test Cases
All 10-random-00.txt, 10-random-01.txt, 10-random-02.txt, 10-random-03.txt, 10-random-04.txt, 20-absW-00.txt, 20-absW-01.txt, 20-absW-02.txt, 20-absW-03.txt, 20-absW-04.txt, 30-balance-00.txt, 30-balance-01.txt, 30-balance-02.txt, 30-balance-03.txt, 30-balance-04.txt, 40-limit_dim-00.txt, 40-limit_dim-01.txt, 40-limit_dim-02.txt, 40-limit_dim-03.txt, 40-limit_dim-04.txt, 40-limit_dim-05.txt, 40-limit_dim-06.txt, Corner1.txt, Sample1.txt
Case Name Status Exec Time Memory
10-random-00.txt AC 115 ms 11532 KB
10-random-01.txt AC 14 ms 11520 KB
10-random-02.txt AC 75 ms 11524 KB
10-random-03.txt AC 91 ms 11528 KB
10-random-04.txt AC 38 ms 11528 KB
20-absW-00.txt AC 113 ms 11524 KB
20-absW-01.txt AC 12 ms 11484 KB
20-absW-02.txt AC 60 ms 11524 KB
20-absW-03.txt AC 99 ms 11552 KB
20-absW-04.txt AC 49 ms 11484 KB
30-balance-00.txt AC 113 ms 11476 KB
30-balance-01.txt AC 14 ms 11520 KB
30-balance-02.txt AC 48 ms 11480 KB
30-balance-03.txt AC 61 ms 11516 KB
30-balance-04.txt AC 95 ms 11544 KB
40-limit_dim-00.txt AC 109 ms 11560 KB
40-limit_dim-01.txt AC 109 ms 11528 KB
40-limit_dim-02.txt AC 108 ms 11524 KB
40-limit_dim-03.txt AC 113 ms 11512 KB
40-limit_dim-04.txt AC 111 ms 11524 KB
40-limit_dim-05.txt AC 105 ms 11520 KB
40-limit_dim-06.txt AC 106 ms 11532 KB
Corner1.txt AC 20 ms 11524 KB
Sample1.txt AC 14 ms 11520 KB