oj.uz

Submission #628363

# Submission time Handle Problem Language Result Execution time Memory
628363 2022-08-13T10:55:33 Z abeker Catfish Farm (IOI22_fish) C++17
9 / 100
 549 ms 52424 KB 
#include <bits/stdc++.h>
#include "fish.h"
using namespace std;

typedef long long ll;

const ll INF = 1e18;

ll max_weights(int N, int M, vector <int> x, vector <int> y, vector <int> w) {
  for (auto &it : x)
    it++;
  vector <ll> sum(N + 2);
  vector <map <int, ll>> diff(N + 2);
  for (int i = 0; i < M; i++) {
    sum[x[i]] += w[i];
    diff[x[i] + 1][y[i]] += w[i];
    diff[x[i]][y[i]] -= w[i];
  }
  vector <pair <int, int>> edges;
  for (int i = 0; i < 5; i++)
    edges.emplace_back(i, (i + 1) % 5);
  for (auto it : {0, 1, 4})
    edges.emplace_back(it, it);
  edges.emplace_back(0, 3);
  edges.emplace_back(2, 0);
  vector <ll> dp(5);
  dp[3] = dp[4] = -INF;
  for (int i = 1; ; i++) {
    auto update = [&](ll &ref, ll val) {
      if (val > ref)
        ref = val;
    };
    ll curr = 0;
    vector <ll> trans(5);
    for (auto it : diff[i]) {
      curr += it.second;
      update(trans[1], curr);
      update(trans[4], -curr);
    }
    trans[2] = sum[i - 1];
    trans[3] = sum[i];
    for (int j = 0; j < 5; j++)
      dp[j] += trans[j];
    if (i == N + 1)
      break;
    vector <ll> nxt(5, -INF);
    for (auto it : edges)
      update(nxt[it.second], dp[it.first]);
    dp = nxt;
  }
  return max({dp[0], dp[3], dp[4], 0ll});
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 18604 KB Output is correct
2 Correct 143 ms 21156 KB Output is correct
3 Correct 9 ms 5716 KB Output is correct
4 Correct 9 ms 5716 KB Output is correct
5 Correct 549 ms 52424 KB Output is correct
6 Correct 356 ms 52212 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 256 ms 27536 KB Output is correct
3 Correct 370 ms 29156 KB Output is correct
4 Correct 119 ms 17228 KB Output is correct
5 Correct 190 ms 20548 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 8 ms 5792 KB Output is correct
11 Correct 9 ms 5716 KB Output is correct
12 Correct 111 ms 17344 KB Output is correct
13 Correct 162 ms 20560 KB Output is correct
14 Correct 115 ms 17260 KB Output is correct
15 Correct 119 ms 16604 KB Output is correct
16 Correct 141 ms 17304 KB Output is correct
17 Correct 139 ms 19032 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5716 KB Output is correct
2 Correct 9 ms 5716 KB Output is correct
3 Incorrect 34 ms 11056 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '17525101486578'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '159432895765'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '159432895765'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '159432895765'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5716 KB Output is correct
2 Correct 9 ms 5716 KB Output is correct
3 Incorrect 34 ms 11056 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '17525101486578'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 18604 KB Output is correct
2 Correct 143 ms 21156 KB Output is correct
3 Correct 9 ms 5716 KB Output is correct
4 Correct 9 ms 5716 KB Output is correct
5 Correct 549 ms 52424 KB Output is correct
6 Correct 356 ms 52212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 256 ms 27536 KB Output is correct
9 Correct 370 ms 29156 KB Output is correct
10 Correct 119 ms 17228 KB Output is correct
11 Correct 190 ms 20548 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 8 ms 5792 KB Output is correct
17 Correct 9 ms 5716 KB Output is correct
18 Correct 111 ms 17344 KB Output is correct
19 Correct 162 ms 20560 KB Output is correct
20 Correct 115 ms 17260 KB Output is correct
21 Correct 119 ms 16604 KB Output is correct
22 Correct 141 ms 17304 KB Output is correct
23 Correct 139 ms 19032 KB Output is correct
24 Correct 9 ms 5716 KB Output is correct
25 Correct 9 ms 5716 KB Output is correct
26 Incorrect 34 ms 11056 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '17525101486578'
27 Halted 0 ms 0 KB -