제출 #274783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
274783		tincamatei	구경하기 (JOI13_watching)	C++14	100 / 100	829 ms	16120 KiB

watching

    #include <bits/stdc++.h>
     
    using namespace std;
     
    const int MAX_N = 2000;
     
    int v[MAX_N];
    int smallNext[1+MAX_N], bigNext[1+MAX_N];
    int dp[1+MAX_N][1+MAX_N];
     
    void getNexts(int n, int w, int *nextP) {
    	int lastp = 0;
    	for(int i = 0; i < n; ++i) {
    		while(lastp < n - 1 && v[lastp + 1] < v[i] + w)
    			++lastp;
    		nextP[i] = lastp;
    	}
     
    	nextP[n] = n - 1;
    }
     
    void runDp(int n, int w) {
    	getNexts(n, w, smallNext);
    	getNexts(n, 2 * w, bigNext);
    	
    	for(int i = 0; i <= n; ++i)
    		for(int j = 0; j <= n; ++j) {
    			dp[i][j] = 0;
    			if(i > 0)
    				dp[i][j] = max(dp[i][j], smallNext[dp[i - 1][j]] + 1);
    			if(j > 0)
    				dp[i][j] = max(dp[i][j], bigNext[dp[i][j - 1]] + 1);
    		}
    }
     
    int main() {
    #ifdef HOME
    	FILE *fin = fopen("input.in", "r");
    	FILE *fout = fopen("output.out", "w");
    #else
    	FILE *fin = stdin;
    	FILE *fout = stdout;
    #endif
     
    	int n, p, q, st, dr;
    	
    	fscanf(fin, "%d%d%d", &n, &p, &q);
    	for(int i = 0; i < n; ++i)
    		fscanf(fin, "%d", &v[i]);
     
    	sort(v, v + n);
     
    	st = 0;
    	dr = 1000000000;
     
    	while(dr - st > 1) {
    		int mid = (st + dr) / 2;
    		runDp(n, mid);
    		
    		if(dp[min(p, n)][min(q, n)] == n)
    			dr = mid;
    		else
    			st = mid;
    	}
    	
    	fprintf(fout, "%d", dr);
     
    	fclose(fin);
    	fclose(fout);
    	return 0;
    }

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

watching.cpp: In function 'int main()':
watching.cpp:47:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |      fscanf(fin, "%d%d%d", &n, &p, &q);
      |      ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:49:13: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |       fscanf(fin, "%d", &v[i]);
      |       ~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50