Submission #105799

#TimeUsernameProblemLanguageResultExecution timeMemory
105799gs18103먼 별 (KOI16_dist)C++98
42 / 100
95 ms636 KiB
#include <bits/stdc++.h> using namespace std; long long arr[1010][4]; long long ans; int n, T; long long dp[10101010]; long long cal_dis(int t) { if(dp[t] != 0) return dp[t]; long long dis = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++) { dis = max(dis, (arr[i][0]-arr[j][0]+t*(arr[i][2]-arr[j][2]))*(arr[i][0]-arr[j][0]+t*(arr[i][2]-arr[j][2]))+ (arr[i][1]-arr[j][1]+t*(arr[i][3]-arr[j][3]))*(arr[i][1]-arr[j][1]+t*(arr[i][3]-arr[j][3]))); } } return dp[t] = dis; } int search(int s, int e) { if(s + 5 >= e) { long long dis = 10000000000000000LL; for(int i = s; i <= e; i++) dis = min(dis, cal_dis(i)); for(int i = s; i <= e; i++) if(dis == cal_dis(i)) return i; } int t1 = (2 * s + e) / 3, t2 = (s + 2 * e) / 3; long long dis1 = cal_dis(t1), dis2 = cal_dis(t2); if(dis1 <= dis2) return search(s, t2); else return search(t1, e); } int main() { scanf("%d %d", &n, &T); for(int i = 0; i < n; i++) for(int j = 0; j < 4; j++) scanf("%lld", &arr[i][j]); int ans = search(0, T); printf("%d\n%lld", ans, cal_dis(ans)); }

Compilation message (stderr)

dist.cpp: In function 'int main()':
dist.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &T);
  ~~~~~^~~~~~~~~~~~~~~~~
dist.cpp:46:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld", &arr[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...