oj.uz

Submission #946578

# Submission time Handle Problem Language Result Execution time Memory
946578 2024-03-14T18:57:46 Z PagodePaiva Meetings (IOI18_meetings) C++17
19 / 100
 3676 ms 786436 KB 
#include "meetings.h"
#include<bits/stdc++.h>
#define ll long long
#define N 5010
#define inf 1e18

using namespace std;

ll pref[N][N];
ll suf[N][N];
ll v[N][N];

std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l,
                                     std::vector<int> r) {
  int n = h.size();
  for(int i = 0;i < n;i++){
    v[i][i] = h[i];
    for(int j = i-1;j >= 0;j--) v[j][i] = max(v[j+1][i], (long long) h[j]);
    for(int j = i+1;j < n;j++) v[j][i] = max(v[j-1][i], (long long) h[j]);
  }
  for(int i = 0;i < n;i++){
    pref[i][i] = v[i][i];
    suf[i][i] = v[i][i];
    for(int j = i-1;j >= 0;j--) pref[j][i] = pref[j+1][i] + v[j][i];
    for(int j = i+1;j < n;j++) suf[j][i] = suf[j-1][i] + v[j][i];
  }
  vector <long long> resp;
  for(int i = 0;i < l.size();i++){
    int lt = l[i], rt = r[i];
    ll res = inf;
    for(int x = lt;x <= rt;x++){
      // cout << pref[lt][x] << ' ' << suf[rt][x] << ' ' << v[x][x] << endl;
      res = min(res, pref[lt][x] + suf[rt][x] - v[x][x]);
    }
    resp.push_back(res);
  }
  return resp;
}

Compilation message

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int i = 0;i < l.size();i++){
      |                 ~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 232 ms 343456 KB Output is correct
3 Correct 156 ms 341732 KB Output is correct
4 Correct 153 ms 343312 KB Output is correct
5 Correct 152 ms 341700 KB Output is correct
6 Correct 154 ms 341840 KB Output is correct
7 Correct 148 ms 343380 KB Output is correct
8 Correct 157 ms 341648 KB Output is correct
9 Correct 150 ms 341616 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 232 ms 343456 KB Output is correct
3 Correct 156 ms 341732 KB Output is correct
4 Correct 153 ms 343312 KB Output is correct
5 Correct 152 ms 341700 KB Output is correct
6 Correct 154 ms 341840 KB Output is correct
7 Correct 148 ms 343380 KB Output is correct
8 Correct 157 ms 341648 KB Output is correct
9 Correct 150 ms 341616 KB Output is correct
10 Correct 617 ms 507680 KB Output is correct
11 Correct 745 ms 507320 KB Output is correct
12 Correct 634 ms 507612 KB Output is correct
13 Correct 741 ms 507472 KB Output is correct
14 Correct 632 ms 507444 KB Output is correct
15 Correct 638 ms 507320 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Runtime error 3676 ms 786436 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Runtime error 3676 ms 786436 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 232 ms 343456 KB Output is correct
3 Correct 156 ms 341732 KB Output is correct
4 Correct 153 ms 343312 KB Output is correct
5 Correct 152 ms 341700 KB Output is correct
6 Correct 154 ms 341840 KB Output is correct
7 Correct 148 ms 343380 KB Output is correct
8 Correct 157 ms 341648 KB Output is correct
9 Correct 150 ms 341616 KB Output is correct
10 Correct 617 ms 507680 KB Output is correct
11 Correct 745 ms 507320 KB Output is correct
12 Correct 634 ms 507612 KB Output is correct
13 Correct 741 ms 507472 KB Output is correct
14 Correct 632 ms 507444 KB Output is correct
15 Correct 638 ms 507320 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Runtime error 3676 ms 786436 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -