| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 925253 | IS_Rushdi | Catfish Farm (IOI22_fish) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
long long max_weights(int n,int m,vector<int>x,vector<int>y,vector<int>w){
long long dp[n+1][4][4]{};
vector<pair<long long,long long>>to[n+1];
for(long long i = 0; i < m; i++){to[x[i]+1].push_back({y[i]+1,w[i]});}
for(long long i = 0; i <= n; i++){
to[i].push_back({0,0});
to[i].push_back({n,0});
}
for(long long i = 0; i < 4; i++){
for(long long j = 0; j < 4; j++){
dp[0][i][j] = -1e18;
}
}
dp[0][0][0] = 0;
long long ans = 0;
for(long long i = 1; i <= n; i++){
for(long long j = 0; j < to[max(i-2,0)].size(); j++){
for(long long k = 0; k < to[i-1].size(); k++){
for(long long v = 0; v < to[i].size(); v++){
long long now = dp[i-1][k][j];
long long cur = to[i][v].first;
for(auto nodes : to[i-1]){
if(cur > max(to[i-2][j].first,to[i-1][k].first)){
if(nodes.first > max(to[i-2][j].first,to[i-1][k].first)){
now += nodes.second;
}
}
}
cur = to[i-1][k].first;
for(auto nodes : to[i]){
if(cur > to[i][v].first){
if(nodes.first > to[i][v].first){
now += nodes.second;
}
}
}
dp[i][v][k] = max(dp[i][v][k],now);
ans = max(ans,now);
}
}
}
}
return ans;
}
// long long main(){
// cout << max_weights(5, 4, {0, 1, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3}) << '\n';
// }