oj.uz

Submission #374223

# Submission time Handle Problem Language Result Execution time Memory
374223 2021-03-06T23:17:49 Z Mamnoon_Siam Two Dishes (JOI19_dishes) C++17
10 / 100
 12 ms 876 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;
const ll inf = 1e18;

int n, m;
ll A[N], B[N], S[N], T[N], P[N], Q[N];
vector<pair<int, ll>> donburi[N], curry[N];
ll dp[N];

void chkmax(ll& x, ll y) { x = max(x, y); }

void CHKMAX(int l, int r, ll x) {
  for(int i = l; i <= r; ++i)
    chkmax(dp[i], x);
}

void range_add(int l, int r, ll x) {
  for(int i = l; i <= r; ++i)
    dp[i] += x;
}

ll range_max(int l, int r) {
  ll ret = 0;
  for(int i = l; i <= r; ++i)
    chkmax(ret, dp[i]);
  return ret;
}

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(int i = 1; i <= n; ++i) { // OK
    if(S[i] < A[i]) continue;
    int j = int(upper_bound(B, B+m+1, S[i] - A[i]) - B - 1);
    donburi[i].emplace_back(j, P[i]);
    debug("donburi", i, j, P[i]);
  }
  for(int i = 1; i <= m; ++i) { // OK
    if(T[i] < B[i]) continue;
    int j = int(upper_bound(A, A+n+1, T[i] - B[i]) - A - 1);
    curry[j].emplace_back(i, Q[i]);
    debug("curry", j, i, Q[i]);
  }

  for(auto [r, val] : donburi[0])
    range_add(0, m, val);
  for(auto [l, val] : curry[0])
    range_add(l, m, val);

  debug(vector<ll>(dp, dp+1+m));

  for(int x = 1; x <= n; ++x) {
    for(auto [r, val] : donburi[x]) {
      range_add(0, r, val);
    }
    for(auto [l, val] : curry[x]) {
      range_add(l, m, val);
    }
    sort(all(curry[x]));
    vi v, cv;
    for(auto [y, val] : donburi[x])
      v.emplace_back(y);
    for(auto [y, val] : curry[x])
      v.emplace_back(y), cv.emplace_back(y);
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    sort(all(cv));
    cv.erase(unique(all(cv)), cv.end());
    cv.emplace_back(m+1);
    for(int y : v) {
      int y2 = *upper_bound(all(cv), y);
      CHKMAX(y, y2, dp[y]);
    }
    for(auto [y, val] : curry[x]) {
      ll ex = range_max(0, y-1);
      CHKMAX(y, m, val + ex);
    }
    debug(vector<ll>(dp, dp+1+m));
  }

  printf("%lld\n", dp[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:103:5: note: in expansion of macro 'debug'
  103 |     debug("donburi", i, j, P[i]);
      |     ^~~~~
dishes.cpp:55:20: warning: statement has no effect [-Wunused-value]
   55 | #define debug(...) 42
      |                    ^~
dishes.cpp:109:5: note: in expansion of macro 'debug'
  109 |     debug("curry", j, i, Q[i]);
      |     ^~~~~
dishes.cpp:55:20: warning: statement has no effect [-Wunused-value]
   55 | #define debug(...) 42
      |                    ^~
dishes.cpp:117:3: note: in expansion of macro 'debug'
  117 |   debug(vector<ll>(dp, dp+1+m));
      |   ^~~~~
dishes.cpp:55:20: warning: statement has no effect [-Wunused-value]
   55 | #define debug(...) 42
      |                    ^~
dishes.cpp:145:5: note: in expansion of macro 'debug'
  145 |     debug(vector<ll>(dp, dp+1+m));
      |     ^~~~~
dishes.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
dishes.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   92 |     scanf("%lld %lld %lld", &A[i], &S[i], &P[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |     scanf("%lld %lld %lld", &B[i], &T[i], &Q[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 876 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 384 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 9 ms 620 KB Output is correct
18 Correct 4 ms 620 KB Output is correct
19 Correct 12 ms 620 KB Output is correct
20 Correct 7 ms 620 KB Output is correct
21 Correct 11 ms 620 KB Output is correct
22 Correct 11 ms 620 KB Output is correct
23 Correct 11 ms 620 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 9 ms 620 KB Output is correct
18 Correct 4 ms 620 KB Output is correct
19 Correct 12 ms 620 KB Output is correct
20 Correct 7 ms 620 KB Output is correct
21 Correct 11 ms 620 KB Output is correct
22 Correct 11 ms 620 KB Output is correct
23 Correct 11 ms 620 KB Output is correct
24 Execution timed out 4 ms 492 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 384 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 9 ms 620 KB Output is correct
18 Correct 4 ms 620 KB Output is correct
19 Correct 12 ms 620 KB Output is correct
20 Correct 7 ms 620 KB Output is correct
21 Correct 11 ms 620 KB Output is correct
22 Correct 11 ms 620 KB Output is correct
23 Correct 11 ms 620 KB Output is correct
24 Execution timed out 4 ms 492 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 384 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 9 ms 620 KB Output is correct
18 Correct 4 ms 620 KB Output is correct
19 Correct 12 ms 620 KB Output is correct
20 Correct 7 ms 620 KB Output is correct
21 Correct 11 ms 620 KB Output is correct
22 Correct 11 ms 620 KB Output is correct
23 Correct 11 ms 620 KB Output is correct
24 Execution timed out 4 ms 492 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 4 ms 876 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 4 ms 876 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -