こちらではpaiza事務局側で作成した模範解答を掲載していす。
提出された最速コードは下記リンク先でご覧いただけます。
C: paiza事務局作成コード Vol.3 O(DN)
通過テストケース数:3
実行時間(テストケース1):0.01秒
実行時間(テストケース2):0.01秒
実行時間(テストケース3):0.67秒
#include <stdio.h> #include <stdlib.h> int CompareInt(const void *_v1, const void *_v2) { int v1 = *((const int *)_v1); int v2 = *((const int *)_v2); if (v1 == v2) return 0; return v1 > v2 ? 1 : -1; } int main(void) { int N, D; scanf("%d %d", &N, &D); int p[500000]; int i; for(i = 0; i < N; i++) { scanf("%d", &p[i]); } qsort(p, N, sizeof(int), CompareInt); for(i = 0; i < D; i++) { int m; scanf("%d", &m); int h = 0, t = N - 1; int ans = 0; while(h != t) { int s = p[h] + p[t]; if (s > m) t--; else { if (ans < s) ans = s; h++; } } printf("%d\n", ans); } return 0; }
C: paiza事務局作成コード Vol.2 O(DNlogN)
通過テストケース数:2
実行時間(テストケース1):0.01秒
実行時間(テストケース2):0.04秒
実行時間(テストケース3):--
#include <stdio.h> #include <stdlib.h> int CompareInt(const void *_v1, const void *_v2) { int v1 = *((const int *)_v1); int v2 = *((const int *)_v2); if (v1 == v2) return 0; return v1 > v2 ? 1 : -1; } int UpperBound(int *p, int N, int r) { int lb = 0, ub = N; //[lb, ub) while(ub - lb != 1) { int mid = (ub + lb) / 2; if (p[mid] <= r) lb = mid; else ub = mid; } return ub; } int main(void) { int N, D; scanf("%d %d", &N, &D); int p[500000]; int i,j; for(i = 0; i < N; i++) { scanf("%d", &p[i]); } qsort(p, N, sizeof(int), CompareInt); for(i = 0; i < D; i++) { int m; scanf("%d", &m); int ans = 0; for(j = 0; j < N; j++) { int r = m - p[j]; int ub = UpperBound(p, N, r); ub--; if (j >= ub) continue; if (p[ub] > r) continue; int s = p[j] + p[ub]; if (s <= m && ans < s) { ans = s; } } printf("%d\n", ans); } return 0; }
C: paiza事務局作成コード Vol.1 O(DN^2)
通過テストケース数:1
実行時間(テストケース1):0.08秒
実行時間(テストケース2):--
実行時間(テストケース3):--
#include <stdio.h> int main(void) { int N, D; scanf("%d %d", &N, &D); int p[500000]; int i, j, k; for(i = 0; i < N; i++) { scanf("%d", &p[i]); } for(i = 0; i < D; i++) { int m; scanf("%d", &m); int ans = 0; for(j = 0; j < N; j++) { for(k = j + 1; k < N; k++) { int s = p[j] + p[k]; if (s > m) continue; if (ans < s) ans = s; } } printf("%d\n", ans); } return 0; }