제출 #1146388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146388		8pete8	Ski 2 (JOI24_ski2)	C++20	86 / 100	1980 ms	465704 KiB

Main

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
#define double long double
using namespace std;
const int mod=1e9+7,mxn=303+5,inf=1e18,minf=-1e18,lg=30;
//#undef int
int n,k,m,x,q,y;
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
int H[mxn+10],C[mxn+10],cnt[2*mxn+10];
int cost[2*mxn+10];
int dp[2*mxn+10][mxn+10][mxn+10];
struct seg{
	int v[2*mxn+10];
	void init(){for(int i=0;i<=2*n+2;i++)v[i]=inf;}
	void update(int pos,int val){
		pos+=n+1;
		v[pos]=val;
		for(int i=pos;i>0;i>>=1)v[i>>1]=min(v[i],v[i^1]);
	}
	int qry(int l,int r){
		int ans=inf;
		for(l+=n+1,r+=n+1;l<=r;l>>=1,r>>=1){
			if(l&1)ans=min(ans,v[l++]);
			if(!(r&1))ans=min(ans,v[r--]);
		}
		return ans;
	}
}t;
int32_t main(){
    fastio
	cin>>n>>k;
	int ans=inf;
	for(int i=0;i<=2*mxn;i++)cost[i]=inf;
	for(int i=1;i<=n;i++){
		cin>>H[i]>>C[i];
		cnt[H[i]]++;
		cost[H[i]]=min(cost[H[i]],C[i]);
	}
	for(int i=1;i<=2*mxn;i++)cost[i]=min(cost[i-1],cost[i]);
	for(int h=0;h<=2*mxn;h++){
		for(int have=n;have>=0;have--)for(int head=0;head<=n;head++)dp[h][have][head]=inf;
	}
	t.init();
	dp[0][0][0]=0;
	for(int h=0;h<=2*mxn;h++){
		int yes=1;
		if(cnt[h]){
			yes=0;
			for(int have=n;have>=0;have--)for(int head=0;head<=n;head++){
				//add cnt into have
				//adding one cus we fix one of them to be main chain
				if(have-cnt[h]+1>=0)dp[h][have][head]=dp[h][have-cnt[h]+1][head];
				else dp[h][have][head]=inf;
			}
		}
		for(int head=0;head<=n;head++){
			for(int have=0;have<=n;have++){
				t.update(have,dp[h][have][head]);
			}
			for(int have=0;have<=n;have++){
				//removing head from have
				//adding yes because we can attach to the main chain for free
				//we need min from have-have+head+yes
				dp[h][have][head]=t.qry(have,min(n,have+head+yes));
				/*
				if(have+head+yes<=n){
					for(int j=have;j<=min(n,have+head+yes);j++)dp[h][have][head]=min(dp[h][have][head],dp[h][j][head]);
				}*/
			}
		}
		for(int have=n;have>=0;have--)for(int head=0;head<=n;head++){
			//creating new head
			
			if(head&&h&&have+1<=n)dp[h][have][head]=min(dp[h][have][head],dp[h][have+1][head-1]+cost[h-1]);
		}
		for(int have=n;have>=0;have--)for(int head=0;head<=n;head++){
			
			dp[h+1][have][head]=min(dp[h+1][have][head],dp[h][have][head]+have*k);
		}
	}
	for(int i=0;i<=n;i++)ans=min(ans,dp[2*mxn][0][i]);
	cout<<ans;
}
/*
dp[hi][have][head]
606 x 303 x 303

there has to be 1 fix main chain
where for each height the node with min cost will not move?
*/

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
Main.cpp:39:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   39 | void setIO(string name){
      |                       ^
Main.cpp:49:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   49 |         void init(){for(int i=0;i<=2*n+2;i++)v[i]=inf;}
      |                   ^
Main.cpp:50:36: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   50 |         void update(int pos,int val){
      |                                    ^
Main.cpp:55:28: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   55 |         int qry(int l,int r){
      |                            ^
Main.cpp:64:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   64 | int32_t main(){
      |              ^
Main.cpp: In function 'void setIO(std::string)':
Main.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 33 / 33
• Subtask 5: 27 / 27
• Subtask 6: 0 / 14