oj.uz

Submission #31184

# Submission time Handle Problem Language Result Execution time Memory
31184 2017-08-13T05:59:42 Z leejseo None (KOI16_dist) C++
0 / 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)/3;
    if (g(llh) <= g(lhh)) hi = llh - 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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1584 KB Output is correct
2 Incorrect 0 ms 1584 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1584 KB Output is correct
2 Incorrect 0 ms 1584 KB Output isn't correct
3 Halted 0 ms 0 KB -

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 Incorrect 0 ms 1584 KB Output isn't correct
3 Halted 0 ms 0 KB -