| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 859465 | kim | 메기 농장 (IOI22_fish) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
struct A{
int x,y,w;
A(int x_,int y_,int w_):x(x_),y(y_),w(w_){}
static bool cmpX(const A&l,const A&r){
if(l.x==r.x) return l.y<r.y;
return l.x<r.x;
}
static bool cmpY(const A&l,const A&r){
if(l.y==r.y) return l.x<r.x;
return l.y<r.y;
}
};
vector<A> fish;
int dp[100005][3];
int n,m;
vector<pii> fx[100005],fy[100005];
ll max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W) {
n=N;
m=M;
int sum=0;
for(int i=0;i<M;++i){
fish.emplace_back(X[i],Y[i],W[i]);
if(Y[1]==1) sum+=W[i];
fx[X[i]].emplace_back(Y[i],W[i]);
fy[Y[i]].emplace_back(X[i],W[i]);
if(X[i]==0) dp[0][1]=W[i];
}
sort(fish.begin(),fish.end(),A::cmpY);
for(int i=1;i<N;++i){
dp[i][0]=max({dp[i-1][0],dp[i-1][1],dp[i-1][2]});
if(fx[i].size()){
dp[i][1]=dp[i-1][0]+fx[i][0].s;
if(i>1) dp[i][2]=dp[i-1][1]+fx[i][0].s;
else dp[i][2]=0;
}
else dp[i][1]=dp[i][2]=0;
}
return max(dp[N-1][1],dp[N-1][0]);
return 0;
}