답안 #29735

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29735 2017-07-20T11:50:49 Z TAMREF 리조트 (KOI16_resort) C++11
100 / 100
0 ms 2064 KB
#include <bits/stdc++.h>
using namespace std;
const int mx=108, inf=1e9;
int dp[mx][mx], mark[mx], N, M;
void input(){
    for(int a=scanf("%d%d",&N,&M);M--;){
        scanf("%d",&a);
        mark[a]=1;
    }
    for(int i=0;i<mx;i++) for(int j=0;j<mx;j++) dp[i][j]=inf;
}
//dp[i][j] : i일째를 보내야 하는데 쿠폰이 j개 남은 상황에서의 최소 비용
void pro(){
    dp[1][0]=0;
    for(int i=1;i<=N;i++){
        if(mark[i]) for(int j=0;j<=i;j++) dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
        else{
            for(int j=0;j<=i;j++){
                dp[i+1][j]=min(dp[i+1][j],dp[i][j]+10);
                for(int t=1;t<=3;t++)
                    dp[i+t][j+1]=min(dp[i+t][j+1],dp[i][j]+25);
                for(int t=1;t<=5;t++)
                    dp[i+t][j+2]=min(dp[i+t][j+2],dp[i][j]+37);
                if(j>2) dp[i+1][j-3]=min(dp[i+1][j-3],dp[i][j]);
            }
        }
    }
    int val=inf;
    /*
    for(int i=1;i<=N+5;i++,puts("")){
        if(mark[i]) puts("----------------------");
        for(int j=0;j<=i;j++) printf("%d ",dp[i][j]==inf?-1:dp[i][j]);
        if(mark[i]) fputs("\n----------------------",stdout);
    }*/
    for(int i=N+1;i<=N+5;i++)
        for(int j=0;j<=i;j++)
            val=min(val,dp[i][j]);
    printf("%d\n",val*1000);
}
int main(){
    input();
    pro();
}

Compilation message

resort.cpp: In function 'void input()':
resort.cpp:7:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a);
                       ^
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2064 KB Output is correct
2 Correct 0 ms 2064 KB Output is correct
3 Correct 0 ms 2064 KB Output is correct
4 Correct 0 ms 2064 KB Output is correct
5 Correct 0 ms 2064 KB Output is correct
6 Correct 0 ms 2064 KB Output is correct
7 Correct 0 ms 2064 KB Output is correct
8 Correct 0 ms 2064 KB Output is correct
9 Correct 0 ms 2064 KB Output is correct
10 Correct 0 ms 2064 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2064 KB Output is correct
2 Correct 0 ms 2064 KB Output is correct
3 Correct 0 ms 2064 KB Output is correct
4 Correct 0 ms 2064 KB Output is correct
5 Correct 0 ms 2064 KB Output is correct
6 Correct 0 ms 2064 KB Output is correct
7 Correct 0 ms 2064 KB Output is correct
8 Correct 0 ms 2064 KB Output is correct
9 Correct 0 ms 2064 KB Output is correct
10 Correct 0 ms 2064 KB Output is correct
11 Correct 0 ms 2064 KB Output is correct
12 Correct 0 ms 2064 KB Output is correct
13 Correct 0 ms 2064 KB Output is correct
14 Correct 0 ms 2064 KB Output is correct
15 Correct 0 ms 2064 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2064 KB Output is correct
2 Correct 0 ms 2064 KB Output is correct
3 Correct 0 ms 2064 KB Output is correct
4 Correct 0 ms 2064 KB Output is correct
5 Correct 0 ms 2064 KB Output is correct
6 Correct 0 ms 2064 KB Output is correct
7 Correct 0 ms 2064 KB Output is correct
8 Correct 0 ms 2064 KB Output is correct
9 Correct 0 ms 2064 KB Output is correct
10 Correct 0 ms 2064 KB Output is correct
11 Correct 0 ms 2064 KB Output is correct
12 Correct 0 ms 2064 KB Output is correct
13 Correct 0 ms 2064 KB Output is correct
14 Correct 0 ms 2064 KB Output is correct
15 Correct 0 ms 2064 KB Output is correct
16 Correct 0 ms 2064 KB Output is correct
17 Correct 0 ms 2064 KB Output is correct
18 Correct 0 ms 2064 KB Output is correct
19 Correct 0 ms 2064 KB Output is correct
20 Correct 0 ms 2064 KB Output is correct
21 Correct 0 ms 2064 KB Output is correct
22 Correct 0 ms 2064 KB Output is correct
23 Correct 0 ms 2064 KB Output is correct
24 Correct 0 ms 2064 KB Output is correct
25 Correct 0 ms 2064 KB Output is correct
26 Correct 0 ms 2064 KB Output is correct
27 Correct 0 ms 2064 KB Output is correct
28 Correct 0 ms 2064 KB Output is correct
29 Correct 0 ms 2064 KB Output is correct
30 Correct 0 ms 2064 KB Output is correct
31 Correct 0 ms 2064 KB Output is correct
32 Correct 0 ms 2064 KB Output is correct
33 Correct 0 ms 2064 KB Output is correct
34 Correct 0 ms 2064 KB Output is correct
35 Correct 0 ms 2064 KB Output is correct
36 Correct 0 ms 2064 KB Output is correct
37 Correct 0 ms 2064 KB Output is correct
38 Correct 0 ms 2064 KB Output is correct
39 Correct 0 ms 2064 KB Output is correct
40 Correct 0 ms 2064 KB Output is correct
41 Correct 0 ms 2064 KB Output is correct
42 Correct 0 ms 2064 KB Output is correct
43 Correct 0 ms 2064 KB Output is correct
44 Correct 0 ms 2064 KB Output is correct