oj.uz

Submission #374183

# Submission time Handle Problem Language Result Execution time Memory
374183 2021-03-06T20:31:32 Z Mamnoon_Siam Two Dishes (JOI19_dishes) C++17
10 / 100
 134 ms 109676 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second

string to_string(string s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int N = 2e3 + 3;

int n, m;
ll A[N], B[N], S[N], T[N], P[N], Q[N];
ll donburi[N][N], curry[N][N];
ll donburi_p[N][N], curry_p[N][N];
ll dp[N][N];

int main(int argc, char const *argv[])
{
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  scanf("%d %d", &n, &m);
  for(int i = 1; i <= n; ++i) {
    scanf("%lld %lld %lld", &A[i], &S[i], &P[i]);
  }
  for(int i = 1; i <= m; ++i) {
    scanf("%lld %lld %lld", &B[i], &T[i], &Q[i]);
  }
  for(ll i = 1, sum = 0; i <= n; ++i) {
    sum += A[i];
    if(sum <= S[i]) {
      int j = 0;
      ll sum2 = 0;
      while(j < m and sum + sum2 + B[j+1] <= S[i]) {
        sum2 += B[++j];
      }
      donburi[i][j] = P[i];
      debug(i, j, P[i]);
    }
  }
  for(ll i = 1, sum = 0; i <= m; ++i) {
    sum += B[i];
    if(sum <= T[i]) {
      int j = 0;
      ll sum2 = 0;
      while(j < n and sum + sum2 + A[j+1] <= T[i]) {
        sum2 += A[++j];
      }
      debug(j, i, Q[i]);
      curry[j][i] = Q[i];
    }
  }
  for(int i = 0; i <= n; ++i) {
    curry_p[i][0] = curry[i][0];
    for(int j = 1; j <= m; ++j)
      curry_p[i][j] = curry_p[i][j-1] + curry[i][j];
    donburi_p[i][m] = donburi[i][m];
    for(int j = m-1; j >= 0; --j) {
      donburi_p[i][j] = donburi_p[i][j+1] + donburi[i][j];
    }
  }

  function<void(ll&,ll)> chkmax = [](ll& x, ll y) {
    x = max(x, y);
  };

  for(int x = 0; x <= n; ++x) {
    for(int y = 0; y <= m; ++y) {
      chkmax(dp[x+1][y], curry_p[x+1][y] + donburi_p[x+1][y] + dp[x][y]);
      chkmax(dp[x][y+1], curry[x][y+1] + dp[x][y]);
    }
  }

  printf("%lld\n", dp[n][m]);

  return 0;
}
/*
* use std::array instead of std::vector, if u can
* overflow?
* array bounds
*/

Compilation message

dishes.cpp: In function 'int main(int, const char**)':
dishes.cpp:55:20: warning: statement has no effect [-Wunused-value]
   55 | #define debug(...) 42
      |                    ^~
dishes.cpp:87:7: note: in expansion of macro 'debug'
   87 |       debug(i, j, P[i]);
      |       ^~~~~
dishes.cpp:55:20: warning: statement has no effect [-Wunused-value]
   55 | #define debug(...) 42
      |                    ^~
dishes.cpp:98:7: note: in expansion of macro 'debug'
   98 |       debug(j, i, Q[i]);
      |       ^~~~~
dishes.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
dishes.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |     scanf("%lld %lld %lld", &A[i], &S[i], &P[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |     scanf("%lld %lld %lld", &B[i], &T[i], &Q[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4 ms 364 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1 ms 640 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 620 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 620 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1 ms 640 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 620 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 620 KB Output is correct
17 Correct 134 ms 102764 KB Output is correct
18 Correct 124 ms 98796 KB Output is correct
19 Correct 126 ms 109292 KB Output is correct
20 Correct 118 ms 102380 KB Output is correct
21 Correct 121 ms 104044 KB Output is correct
22 Correct 130 ms 109676 KB Output is correct
23 Correct 126 ms 109400 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1 ms 640 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 620 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 620 KB Output is correct
17 Correct 134 ms 102764 KB Output is correct
18 Correct 124 ms 98796 KB Output is correct
19 Correct 126 ms 109292 KB Output is correct
20 Correct 118 ms 102380 KB Output is correct
21 Correct 121 ms 104044 KB Output is correct
22 Correct 130 ms 109676 KB Output is correct
23 Correct 126 ms 109400 KB Output is correct
24 Execution timed out 4 ms 748 KB Time limit exceeded (wall clock)
25 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1 ms 640 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 620 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 620 KB Output is correct
17 Correct 134 ms 102764 KB Output is correct
18 Correct 124 ms 98796 KB Output is correct
19 Correct 126 ms 109292 KB Output is correct
20 Correct 118 ms 102380 KB Output is correct
21 Correct 121 ms 104044 KB Output is correct
22 Correct 130 ms 109676 KB Output is correct
23 Correct 126 ms 109400 KB Output is correct
24 Execution timed out 4 ms 748 KB Time limit exceeded (wall clock)
25 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1 ms 640 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 620 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 620 KB Output is correct
17 Correct 134 ms 102764 KB Output is correct
18 Correct 124 ms 98796 KB Output is correct
19 Correct 126 ms 109292 KB Output is correct
20 Correct 118 ms 102380 KB Output is correct
21 Correct 121 ms 104044 KB Output is correct
22 Correct 130 ms 109676 KB Output is correct
23 Correct 126 ms 109400 KB Output is correct
24 Execution timed out 4 ms 748 KB Time limit exceeded (wall clock)
25 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4 ms 364 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4 ms 364 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -