oj.uz

Submission #374188

# Submission time Handle Problem Language Result Execution time Memory
374188 2021-03-06T20:54:16 Z Mamnoon_Siam Two Dishes (JOI19_dishes) C++17
10 / 100
 126 ms 109548 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]);
    A[i] += A[i-1];
  }
  for(int i = 1; i <= m; ++i) {
    scanf("%lld %lld %lld", &B[i], &T[i], &Q[i]);
    B[i] += B[i-1];
  }
  for(ll i = 1, sum = 0; i <= n; ++i) {
    if(S[i] < A[i]) continue;
    int j = int(upper_bound(B, B+m+1, S[i] - A[i]) - B - 1);
    donburi[i][j] = P[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) {
    if(T[i] < B[i]) continue;
    int j = int(upper_bound(A, A+n+1, T[i] - B[i]) - A - 1);
    curry[j][i] = Q[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:80:17: warning: unused variable 'sum' [-Wunused-variable]
   80 |   for(ll i = 1, sum = 0; i <= n; ++i) {
      |                 ^~~
dishes.cpp:95:17: warning: unused variable 'sum' [-Wunused-variable]
   95 |   for(ll i = 1, sum = 0; i <= m; ++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:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |     scanf("%lld %lld %lld", &B[i], &T[i], &Q[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 4460 KB Execution killed with signal 11
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 640 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 620 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 640 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 620 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 123 ms 102636 KB Output is correct
18 Correct 120 ms 98796 KB Output is correct
19 Correct 126 ms 109164 KB Output is correct
20 Correct 121 ms 102336 KB Output is correct
21 Correct 122 ms 103916 KB Output is correct
22 Correct 123 ms 109548 KB Output is correct
23 Correct 122 ms 109420 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 640 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 620 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 123 ms 102636 KB Output is correct
18 Correct 120 ms 98796 KB Output is correct
19 Correct 126 ms 109164 KB Output is correct
20 Correct 121 ms 102336 KB Output is correct
21 Correct 122 ms 103916 KB Output is correct
22 Correct 123 ms 109548 KB Output is correct
23 Correct 122 ms 109420 KB Output is correct
24 Execution timed out 4 ms 364 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 640 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 620 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 123 ms 102636 KB Output is correct
18 Correct 120 ms 98796 KB Output is correct
19 Correct 126 ms 109164 KB Output is correct
20 Correct 121 ms 102336 KB Output is correct
21 Correct 122 ms 103916 KB Output is correct
22 Correct 123 ms 109548 KB Output is correct
23 Correct 122 ms 109420 KB Output is correct
24 Execution timed out 4 ms 364 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 640 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 620 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 123 ms 102636 KB Output is correct
18 Correct 120 ms 98796 KB Output is correct
19 Correct 126 ms 109164 KB Output is correct
20 Correct 121 ms 102336 KB Output is correct
21 Correct 122 ms 103916 KB Output is correct
22 Correct 123 ms 109548 KB Output is correct
23 Correct 122 ms 109420 KB Output is correct
24 Execution timed out 4 ms 364 KB Time limit exceeded (wall clock)
25 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 4460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 4460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -