What's wrong?
#include<cstdio>
using namespace std;
const int N=201;
struct Node{int x,y;}a[N];
struct Line{int s,t;}b[N];
int fa[N],n,m,root;
inline int direct(Node x,Node y,Node z){
    return (y.x-x.x)*(z.y-x.y)-(y.y-x.y)*(z.x-x.x);
}
bool online(Node x,Line y){//right
    Node be=a[y.s],en=a[y.t];
    if (x.x<be.x||x.x>en.x) return 0;
    if (direct(be,x,en)==0) return 1;
    return 0;
}
bool cross(Line x,Line y){
    Node p1=a[x.s],p2=a[x.t],p3=a[y.s],p4=a[y.t];
    if (online(p1,y)||online(p2,y)||online(p3,x)||online(p4,x)) return 1;
    int d1=direct(p1,p2,p3),d2=direct(p1,p2,p4),d3=direct(p3,p4,p1),d4=direct(p3,p4,p2);
    if ((d1^d2)<0&&(d3^d4)<0) return 1;
    return 0;
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void unite(int x,int y){
    x=find(x); y=find(y);
    if (x<y) fa[y]=x; else if (x>y) fa[x]=y;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++) fa[i]=i;
    for (int i=1; i<=n; i++) scanf("%d%d",&a[i].x,&a[i].y);
    for (int i=1; i<=m; i++){
        scanf("%d%d",&b[i].s,&b[i].t); unite(b[i].s,b[i].t);
        for (int j=1; j<=n; j++)if (online(a[j],b[i])) unite(j,b[i].s);
        for (int j=1; j<i; j++) if (cross(b[i],b[j])) unite(b[i].s,b[j].s);
    }
    root=find(1);
    for (int i=2; i<=n; i++) if (find(i)!=root) {printf("NO"); return 0;}
    printf("YES");
    return 0;
}

My algo is O(p*n*logn).

Algo:
1)sort pairs <d,s> by d.  We get d1<=d2<=d3<=...<=dn.
                                 s1  s2  s3       sn
2)For each p we choose a minimal k (if exist pairs <ki,p> and <kj,p> where ki<kj then we delete <kj,p>

3)ans=s[1]+...+s[n]-(x1+x2+...+xn)/100 where xi=s[i]*di or xi=s[i]*p if we choose p (if we choose p => the minimum of the k elements of x are equal to s*p), i=1..n

=> we must max_sum=(x1+x2+...+xn)->max
=>ans=s[1]+...+s[n]-max_sum/100

4)max_sum=s1*d1+...+sn*dn
For each p=1..100 find 1<=j<=n | p<dj, j->min (if there is no such j => max_sum=max(max_sum, (s[1]+...+s[n])*p) )
  then we take (s[1]+...+s[j-1])*p (s[0]=0); if we took <k elements then we must take lost=k-(j-1) elements from sj,...,sn. We must choose such index i1<i2<...<ilost from j..n | s[i1]*(d[i1]-p)=min(s[i]*(d[i]-p), j<=i<=n, s[i2]*(d[i2]-p)=min(s[i]*(d[i]-p), j<=i<=n,i!=i1, ... .
  then max_sum=max(max_sum, (s[1]+...+s[j-1])*p + (s[i1]+...+s[ilost])*p+Sum(si*di, j<=i<=n and i<>ik,k=1..lost)).

Edited by author 28.06.2017 15:34

My solution passes first 4 test cases and shows memory limit exceeded error at 5th test case. I have made a global 4D array 100*100*100*100 which keeps the result of the sum of a rectangle whose top left corner is x1,y1 and bottom right corner is x2,y2, 4d array mat[x1][y1][x2][y2] stores the sum of the numbers corresponding to that rectangle. Now if this big array were a reason behind memory limit exceeded error than it shouldn't have passed even the first test cases because i made global 4d array of maximum size by default. So what can be the reason?

#include <iostream>
using namespace std;

const int M = 107;

int mat[M][M][M][M];

int main() {
    int n;
    cin >> n;
    int arr[n][n];

    int ans = -1e9;

    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++) {
            cin >> arr[i][j];
            mat[i][j][i][j] = arr[i][j];
            if (arr[i][j] > ans) ans = arr[i][j];
        }


    for (int size = 2; size<=n*n; size++) {
        for (int p=1; p<=size and p<=n; p++) {
            int q =  size/p;
            if (p*q != size) continue;


            for (int i=0; i<n-p+1; i++) {
                for (int j=0; j<n-q+1; j++) {

                    int x1 = i,     y1 = j;
                    int x2 = i+p-1, y2 = j+q-1;

                    if (x2-x1 > y2-y1) {
                        mat[x1][y1][x2][y2] = mat[x1][y1][x2-1][y2] + mat[x2][y1][x2][y2];
                        if (mat[x1][y1][x2][y2] > ans) ans = mat[x1][y1][x2][y2];
                    }
                    else {
                        mat[x1][y1][x2][y2] = mat[x1][y1][x2][y2-1] + mat[x1][y2][x2][y2];
                        if (mat[x1][y1][x2][y2] > ans) ans = mat[x1][y1][x2][y2];
                    }

                }
            }



        }
    }

    cout << ans << endl;

}

Edited by author 26.06.2017 17:06

Edited by author 26.06.2017 17:06

Edited by author 26.06.2017 17:07

Why if I am trying to precalculate factorials using unsigned long long int there is WA#5?  There are 64 last binary  digits  digits and in this task we are to output at most 32 binary digits.

There are no tests where N=0 xD)

#include<cstdio>
#include<cstring>
#include<iostream>
#define pii pair<int,int>
#define pdd pair<double,double>
#define mp make_pair
#define F first
#define S second
#define N 210
using namespace std;
int n,m;
int fat[N];
pii e[N];
pdd p[N];
int father(int x) {if(fat[x]!=x) fat[x]=father(fat[x]); return fat[x];}
double calc(pii a,pii b,pii c)  {return (a.F-c.F)*(b.S-c.S)-(b.F-c.F)*(a.S-c.S);}
bool judge(pii a, pii b, pii c, pii d)
{
    if (max(a.F,b.F)<min(c.F,d.F)||max(a.S,b.S)<min(c.S,d.S)||max(c.F,d.F)<min(a.F,b.F)||max(c.S,d.S)<min(a.S,b.S))  return false;
    if (calc(c,b,a)*calc(b,d,a)<0||calc(a,d,c)*calc(d,b,c)<0)  return false;
    return true;
}
int main()
{
    int i,j,x,y;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++) fat[i]=i;
    for(i=1;i<=n;i++) {scanf("%lf %lf",&x,&y); p[i]=mp(x,y);}
    for(i=1;i<=m;i++) {scanf("%d %d",&x,&y); e[i]=mp(x,y); fat[father(x)]=father(y);}
    for(i=m+1;i<=m+n;i++) e[i]=mp(i-m,i-m);
    m+=n;
    for(i=1;i<=m;i++)
        for(j=i+1;j<=m;j++)
            if(judge(p[e[i].F],p[e[i].S],p[e[j].F],p[e[j].S]))
                fat[father(e[i].F)]=father(e[j].F);
    int stan=father(1);
    for(i=1;i<=n;i++) if(father(i)!=stan)
    puts("YES");
    return 0;
}

Just output n random numbers.
After that,  output m random numbers.
All random numbers are in range [1;1e9].
AC first attempt.

At first I wrote a tricky solution using trigonometry and binary search.  And I was unable to pass through test case No.  12.
Then I wrote simple two-step solution and got AC.

Can somebody write input?

I wrote program on C++ and got WA1. I rewrote program on Pascal and got AC.
I think my error in input string. How do i read lines? My attempts:
1)
     int c;
     n=0;
     while ((c = getchar()) != EOF)
     {
          if(c=='\n') break;
          s[++n]=c;
     }
     m=0;
     while ((c = getchar()) != EOF) t[++m]=(char)c;
2)
void Input()
{
     int c;
     scanf("%c",&c);
     n=0;
     while (c!='\n')
     {
          s[++n]=c;
          scanf("%c",&c);
     }
     m=0;
     while ((c = getchar()) != EOF) t[++m]=(char)c;
}

Probably <string> will help, but i prefer work with index>=1.

Edited by author 22.06.2017 23:44

Edited by author 22.06.2017 23:44

Used DP + BIT, AC in 0.078
O(n*k*logn) solution.
Don't forget, % 10^9 every step.

My approach wrong approach is such.
Read cur number X.
Find CNT count of numbers Y (Y>X) already read.
Find number of ways to pick K-1 items from set of CNT distinctive  items.
Add that number to ANSWER. Find modulo.

Edited by author 11.05.2017 13:28

After we add new pile Z of stones if there is new pair of piles X and Y such that |X-Y| is minimal that either X=Z or Y=Z. So,  just add nee pile and recalculate new pair of piles such that the difference between stones count is minimal in O(n)  where n is tje number of piles present now.

import java.util.Scanner;

/**
 * Created by macbookpro on 2/19/15.
 */
public class JavaThieves877 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int c1 = Integer.parseInt(scanner.nextLine());
        int c2 = Integer.parseInt(scanner.nextLine());

        if(c1 % 2==0 || c2 % 2!=0 )
        {
            System.out.print("Yes");
        }
        else if(c1 % 2 != 0 || c2% 2== 0)
        {
            System.out.print("No");
        }
    }
}

Some tests?

At first I thought I was getting WA's because of the wrong minus sign.
Actual reason was printing integers.
I was trying to print integers using just PUTCHAR.
Of course it worked fine for 0-9. And was failing for other numbers.

I tried to solve it with C++.  It was long.  It was PAINFUL!  Finally,  I didn't managed to solve it in C++.  And then I just opened my Python IDE and solves it within 10 minutes.  Just AC first attempt.  The task is evil.

The product of natural numbers with a given condition in this problem will be maximal if and only if the middle arithmetic of these numbers is the most closely to the number e=2.71828... It's a mathematical sentence which are proved!

P.S. Sorry for my bad English

used RMQ using segment tree to find lca in log(n)
total time complexity O(n+q*(lgn)) = O(q*lgn)