oj.uz

Submission #31190

# Submission time Handle Problem Language Result Execution time Memory
31190 2017-08-13T06:06:32 Z leejseo None (KOI16_dist) C++
42 / 100
 2000 ms 1584 KB 
#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
typedef struct {
  int x, y, dx, dy;
} star;
 
#define MAX_T 10000000
#define MAX_N 30000
 
star L[MAX_N];
 
int n, T;
 
long long int dist(star &a, star &b, int t){
  long long int a_x = a.x + t*a.dx;
  long long int a_y = a.y + t*a.dy;
  long long int b_x = b.x + t*b.dx;
  long long int b_y = b.y + t*b.dy;
  return (a_x - b_x)*(a_x - b_x) + (a_y - b_y) * (a_y - b_y);
}
 
long long int g(int t){
  long long cnt = 0;
  for(int i=0; i<n; i++){
    for(int j=0; j<i; j++){
      long long temp = dist(L[i], L[j], t);
      if (temp > cnt){
        cnt = temp;
      }
    }
  }
  return cnt;
}
 
int f(){
  int lo = 0;
  int hi = T;
  while (lo <= hi){
    int llh = (2*lo + hi)/3;
    int lhh = (lo + 2*hi + 1)/3;
    if (g(llh) <= g(lhh)) hi = lhh - 1;
    else lo = llh+1;
  }
  return lo;
}
 
int main(){
  scanf("%d%d", &n, &T);
  for (int i=0; i<n; i++){
    scanf("%d%d%d%d", &(L[i].x), &(L[i].y), &(L[i].dx), &(L[i].dy));
  }
  int day = f();
  long long d = g(day);
  printf("%d\n", day);
  printf("%lld\n", d);
  return 0;
}

Compilation message

dist.cpp: In function 'int main()':
dist.cpp:51:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &T);
                        ^
dist.cpp:53:68: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &(L[i].x), &(L[i].y), &(L[i].dx), &(L[i].dy));
                                                                    ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1584 KB Output is correct
2 Correct 0 ms 1584 KB Output is correct
3 Correct 0 ms 1584 KB Output is correct
4 Correct 0 ms 1584 KB Output is correct
5 Correct 0 ms 1584 KB Output is correct
6 Correct 0 ms 1584 KB Output is correct
7 Correct 0 ms 1584 KB Output is correct
8 Correct 0 ms 1584 KB Output is correct
9 Correct 0 ms 1584 KB Output is correct
10 Correct 0 ms 1584 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1584 KB Output is correct
2 Correct 0 ms 1584 KB Output is correct
3 Correct 0 ms 1584 KB Output is correct
4 Correct 0 ms 1584 KB Output is correct
5 Correct 0 ms 1584 KB Output is correct
6 Correct 0 ms 1584 KB Output is correct
7 Correct 0 ms 1584 KB Output is correct
8 Correct 0 ms 1584 KB Output is correct
9 Correct 0 ms 1584 KB Output is correct
10 Correct 0 ms 1584 KB Output is correct
11 Correct 146 ms 1584 KB Output is correct
12 Correct 113 ms 1584 KB Output is correct
13 Correct 109 ms 1584 KB Output is correct
14 Correct 123 ms 1584 KB Output is correct
15 Correct 106 ms 1584 KB Output is correct
16 Correct 109 ms 1584 KB Output is correct
17 Correct 143 ms 1584 KB Output is correct
18 Correct 99 ms 1584 KB Output is correct
19 Correct 79 ms 1584 KB Output is correct
20 Correct 106 ms 1584 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 1584 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1584 KB Output is correct
2 Correct 0 ms 1584 KB Output is correct
3 Correct 0 ms 1584 KB Output is correct
4 Correct 0 ms 1584 KB Output is correct
5 Correct 0 ms 1584 KB Output is correct
6 Correct 0 ms 1584 KB Output is correct
7 Correct 0 ms 1584 KB Output is correct
8 Correct 0 ms 1584 KB Output is correct
9 Correct 0 ms 1584 KB Output is correct
10 Correct 0 ms 1584 KB Output is correct
11 Correct 146 ms 1584 KB Output is correct
12 Correct 113 ms 1584 KB Output is correct
13 Correct 109 ms 1584 KB Output is correct
14 Correct 123 ms 1584 KB Output is correct
15 Correct 106 ms 1584 KB Output is correct
16 Correct 109 ms 1584 KB Output is correct
17 Correct 143 ms 1584 KB Output is correct
18 Correct 99 ms 1584 KB Output is correct
19 Correct 79 ms 1584 KB Output is correct
20 Correct 106 ms 1584 KB Output is correct
21 Execution timed out 2000 ms 1584 KB Execution timed out
22 Halted 0 ms 0 KB -