oj.uz

답안 #872200

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872200 2023-11-12T13:36:32 Z Ludissey 메기 농장 (IOI22_fish) C++17
23 / 100
 1000 ms 108884 KB 
#include "fish.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
map<pair<int,int>, int> a;
vector<vector<int>> fsh;
vector<vector<int>> cfsh;

map<pair<int,pair<int,int>>, int> memo;
int N,M;
int dp(int x, int last, int lastlast){
  if(memo.find({x,{last,lastlast}})!=memo.end()) return memo[{x,{last,lastlast}}];
  if(x==N) return 0;
 
  memo[{x,{last,lastlast}}] = 0;
  for (auto i:fsh[x])
  {
    int c=dp(x+1, i, last);
    if(x>0){
      for (auto y:cfsh[x-1]) {
        if(y>last&&y<=max(i,lastlast)) c+=a[{x-1,y-1}];
      }
    }
    if(x==N-1) {
      for (auto y:cfsh[x]) {
        if(y>i&&y<=last) c+=a[{x,y-1}];
      }
    }
    memo[{x,{last,lastlast}}]=max(c, memo[{x,{last,lastlast}}]);
  }
  return memo[{x,{last,lastlast}}];
}
 
long long max_weights(signed n, signed m, std::vector<signed> X, std::vector<signed> Y, std::vector<signed> W) {
  N=n; M=m; 
  fsh.resize(N+1, vector<int>(1,0));
  cfsh.resize(N+1);
  for (int i = 0; i < M; i++){
    a[{X[i],Y[i]}] = W[i];

    fsh[X[i]+1].push_back(Y[i]+1);
    cfsh[X[i]].push_back(Y[i]+1);
    if(X[i]>0) {
      fsh[X[i]-1].push_back(Y[i]+1);
    }
  }
  for (int i = 0; i < N; i++) sort(fsh[i].begin(),fsh[i].end());
  
  int p=dp(0,0,0);
  return p;
}

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1047 ms 41860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 1049 ms 50588 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 36188 KB Output is correct
2 Correct 66 ms 36180 KB Output is correct
3 Correct 301 ms 53516 KB Output is correct
4 Correct 236 ms 50344 KB Output is correct
5 Correct 567 ms 73644 KB Output is correct
6 Correct 562 ms 73812 KB Output is correct
7 Correct 561 ms 73832 KB Output is correct
8 Correct 558 ms 73812 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 8 ms 756 KB Output is correct
10 Correct 102 ms 2580 KB Output is correct
11 Correct 27 ms 1112 KB Output is correct
12 Correct 32 ms 1628 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 16 ms 1280 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 8 ms 756 KB Output is correct
10 Correct 102 ms 2580 KB Output is correct
11 Correct 27 ms 1112 KB Output is correct
12 Correct 32 ms 1628 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 16 ms 1280 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Execution timed out 1093 ms 2036 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 8 ms 756 KB Output is correct
10 Correct 102 ms 2580 KB Output is correct
11 Correct 27 ms 1112 KB Output is correct
12 Correct 32 ms 1628 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 16 ms 1280 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Execution timed out 1093 ms 2036 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 36188 KB Output is correct
2 Correct 66 ms 36180 KB Output is correct
3 Correct 301 ms 53516 KB Output is correct
4 Correct 236 ms 50344 KB Output is correct
5 Correct 567 ms 73644 KB Output is correct
6 Correct 562 ms 73812 KB Output is correct
7 Correct 561 ms 73832 KB Output is correct
8 Correct 558 ms 73812 KB Output is correct
9 Execution timed out 1065 ms 108884 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1047 ms 41860 KB Time limit exceeded
2 Halted 0 ms 0 KB -