akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
bool isit(string s)
{
    for(int i=0; i<s.length(); i++)
    {

        if((i+1)%2==1&&!(s[i]=='R'||s[i]=='U'||s[i]=='D'))
            return 0;
        else if((i+1)%2==0&&!(s[i]=='L'||s[i]=='U'||s[i]=='D'))
            return 0;

    }
    return 1;
}
int main()
{
    string s;
    cin>>s;

    if(isit(s))
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

int main() {
    int n;
    cin >> n;
    int a[n+1];
    a[0] = 1001001001;

    int ans = 0;

    srep(i,1,n+1){
        cin >> a[i];
        if(a[i-1] >= a[i])ans++;
    }

    cout << ans << endl;
    cout << n << endl;
    return 0;
}
 
 



Measured memory_bytes: 3476
import java.util.Scanner;

class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    if(a > b){
      int x = a;
      a = b;
      b = x;
    }
    if(b > c){
      int y = b;
      b = c;
      c = y;
    }
    if(a > b){
      int z = a;
      a = b;
      b = z;
    }
    System.out.println(a+" "+b+" "+c);
  }
}



Measured memory_bytes: 26232
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define ll long long
#define mod 100000007
#define rep(i, n) for (int i = 0; i < n; ++i)
ll lcm(ll a, ll b)
{
    return a * b / __gcd(a, b);
}

int main()
{
    int H, W;
    cin >> H >> W;
    vector<int> dh = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
    vector<int> dw = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
    vector<vector<char>> S(H, vector<char>(W));
    rep(i, H)
    {
        rep(j, W)
        {
            cin >> S.at(i).at(j);
        }
    }
    rep(i, H)
    {
        rep(j, W)
        {
            if (S.at(i).at(j) == '#')
            {
                cout << '#';
            }
            else
            {
                int cnt = 0;
                rep(k, 9)
                {
                    int nh = i + dh.at(k);
                    int nw = j + dw.at(k);
                    if (0 <= nh && nh < H && 0 <= nw && nw < W && S.at(nh).at(nw) == '#')
                    {
                        ++cnt;
                    }
                }
                cout << cnt;
            }
        }
        cout << endl;
    }
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define long long ll
using namespace std;


int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
	int s,w;
	cin>>s>>w;
	if(s<=w){
		cout<<"unsafe";
	}
	else cout<<"safe";
    return 0;
}



Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
long long int n,i,j,k;
long long int a[100010][3],dp[100010][3];
long long int solve(long long int index,long long position)
{
    if(index==n-1)
        return dp[index][position]=a[index][position];
    if(dp[index][position]==-1)
    {
        if(position==0)
            return dp[index][position]=a[index][position]+max(solve(index+1,1),solve(index+1,2));
        else if(position==1)
            return dp[index][position]=a[index][position]+max(solve(index+1,0),solve(index+1,2));
        else
            return dp[index][position]=a[index][position]+max(solve(index+1,0),solve(index+1,1));
    }
    else
        return dp[index][position];
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    for(i=0;i<n;i++)
        for(j=0;j<3;j++)
            cin>>a[i][j],dp[i][j]=-1;

    cout<<max(solve(0,0),max(solve(0,1),solve(0,2)));
}



Measured memory_bytes: 9600
#include<iostream>
#include<vector>

using namespace std;

int gcd(int a, int b) {
	if (a == 0)
		return b;
	return gcd(b % a, a);
}

int main() {
	int a;
	cin >> a;
	int sum = 0;
	for (int i = 1; i <= a; i++) {
		for (int j = 1; j <= a; j++) {
			for (int k = 1; k <= a; k++) {
				sum += gcd(i, gcd(j, k));
			}
		}
	}
	cout << sum;
	return 0;
}

Measured memory_bytes: 3600
D=int(input())
c = [int(i) for i in input().split()]
s=[]
for i in range(D):
    s.append([int(j) for j in input().split()])

tst = [0] * 26
last = [0] * 26

ans =[]
for i in range(D):
    a = s[i]
    x,y = 0,0
    for i,v in enumerate(a):
        if x < v:
            x = v
            y = i
    ans.append(y+1)
    tst[y] += a[y]
    last[y] = i+1
    for k in range(26):
        if k != y:
            tst[k] -= (i+1 - last[k])*c[k]
for i in ans:
    print(i)


Measured memory_bytes: 9516
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

#define A cout << "Audrey wins." << endl
#define F cout << "Fabre wins." << endl
 
int c2i(char s){
    return s-'0';
}
 
string c2s(char aa,char bb){
    int a = c2i(aa)+c2i(bb);
    if(a == 0) return "0";
 
    string s = "";
    while(a > 0){
	s += ((a%10)+'0');
	a /= 10;
    }
    reverse(s.begin(),s.end());
    return s;
}
 
int main(){
    int n;
 
    cin >> n;
    while(n--){
	string str;
	cin >> str;
     
	int cnt = 0;
	while(str.size() >= 2){
	    cnt++;
	    int pos = str.size()-2;
	    string tmp = c2s(str[pos],str[pos+1]);
	    if(pos >= 0) str = str.substr(0,pos) + tmp;
	}
	if(cnt%2) F;
	else A;    
    }
    return 0;
}

Measured memory_bytes: 2992
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll t;
    t=1;
    while(t--)
    {
       ll n;
       cin>>n;
       ll arr[n];
       for(int i=0;i<n;i++)
        cin>>arr[i];
       bool fg=true;
       for(int i=0;i<n;i++)
       {
           if(arr[i]%2==0)
           {
               if(arr[i]%3!=0 && arr[i]%5!=0)
                fg=false;
           }
       }
       if(fg)
        cout<<"APPROVED";
       else
        cout<<"DENIED";
    }
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int i;
	long long K, k[2];
	scanf("%lld", &K);
	k[0] = 51 - K % 50;
	k[1] = K / 50 + 49 - K % 50;
	k[2] = K / 50 + 50;
	printf("50\n%lld", k[1]);
	for (i = 2; i < k[0]; i++) printf(" %lld", k[1]);
	for (i = k[0]; i <= 50; i++) printf(" %lld", k[2]);
	printf("\n");
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 128
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
// #define int ll
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[4] ={1,0,-1,0} , dy[4] ={0,1,0,-1};
 
template<class T> 
inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> 
inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
struct Timer{
    chrono::system_clock::time_point start, end;
    Timer(){ start = chrono::system_clock::now(); }
    ~Timer(){
        end = chrono::system_clock::now();
        auto msec = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cerr<<"time : "<<msec<<" ms"<<endl;
    }
};
 

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Timer TM;

    string s;
    cin>>s;
    sort(all(s));
    if(s=="abc") cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

int main() {
  ll n;
  cin >> n;
  vec cnt(n+1);
  ll ans=0;
  for(ll i=1;i<=n;i++) {
    for(ll j=1;j*i<=n;j++) {
      cnt[j*i]++;
    }
    ans+=i*cnt[i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 81400
#include <stdio.h>

int main(void){
	int a,b,c;
	scanf("%d %d %d", &a,&b,&c);
	
	if(a <= b){
		if(b <= c){
			printf("%d %d %d\n" ,a,b,c);
		}else if(a <= c){
			printf("%d %d %d\n" ,a,c,b);
		}else{
			printf("%d %d %d\n" ,c,a,b);
		}
	}else{
		if(a <= c){
			printf("%d %d %d\n" ,b,a,c);
		}else if(b <= c){
			printf("%d %d %d\n" ,b,c,a);
		}else{
			printf("%d %d %d\n" ,c,b,a);
		}
	}
	
	return 0;
}



Measured memory_bytes: 2048
//
// Created by yamunaku on 2020/04/19.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;

int main(){
    //CFS;
    int n, m;
    cin >> n >> m;
    int t=0;
    rep(i, m){
        int x;
        cin >> x;
        t += x;
    }
    if(t > n)cout << -1 << endl;
    else cout << n - t << endl;
    return 0;
}

Measured memory_bytes: 3636
import std.stdio, std.math, std.conv;

void main() {
  for(int a, b; readf("%d %d\n", &a, &b);) {
    int[int] used;
    int len = 0;
    int c;
    bool first = true;
    a %= b;  
    do {
      c = a % b;
      if (first) first = false;
      else write(a / b);
      if (c == 0) break;      
      if (c in used) break;
      else {
        used[c] = len;
        a = c * 10;
      }
      len++;
    } while(true);
    writeln;
    if (c != 0) {
      for(int i = 0; i <= used[c] - 1; i++) write(" ");
      for(int i = used[c] + 1; i <= len; i++) write("^");
      writeln;
    }
  }
}

Measured memory_bytes: 1228
#include <stdio.h>
#include <stdlib.h>

struct Node{
  int key;
  struct Node *right,*left,*parent;
};

struct Node *root,*NIL;

void insert(int k){
  struct Node *y=NIL;
  struct Node *x=root;
  struct Node *z;

  z=(struct Node *)malloc(sizeof(struct Node));
  z->key=k;
  z->left=NIL;
  z->right=NIL;

  while(x!=NIL){
    y=x;
    if(z->key<x->key) x=x->left;
    else x=x->right;
  }
    z->parent=y;
    if(y==NIL)root=z;
    else if(z->key<y->key) y->left=z;
    else y->right=z;
}

struct Node * find(struct Node *x,int k){
  while(x!=NIL && k!=x->key){
    if(k<x->key) x=x->left;
    else x=x->right;
  }
  return x;
}

struct Node * getMinimum(struct Node *x){
  while(x->left!=NIL){
    x=x->left;
  }
  return x;
}

struct Node * getSuccessor(struct Node *x){
  if(x->right!=NIL) return getMinimum(x->right);
  struct Node *y= x->parent;
  while(y!=NIL&&x==y->right){
    x=y;
    y=y->parent;
  }
  return y;
}

void delete(struct Node *z){
  struct Node *y;
  struct Node *x;

  if(z->left==NIL || z->right==NIL){
    y=z;
  } else {
      y=getSuccessor(z);
    }
    if(y->left!=NIL){
      x=y->left;
    } else {
      x=y->right;
    }

    if(x!=NIL){
      x->parent=y->parent;
    }

    if(y->parent==NIL){
      root=x;
    } else {
      if(y==y->parent->left){
        y->parent->left=x;
      } else {
        y->parent->right=x;
    }
}

if (y!=z) {
  z->key=y->key;
}
free(y);
}

void inorder(struct Node *u){
  if(u==NIL) return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}

void preorder(struct Node *u){
  if(u==NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}

int main(){
  int n,i,x;
  struct Node *fi;
  char str[20];

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%s",str);
    if(str[0]=='i'){
      scanf("%d",&x);
      insert(x);
    }
    else if(str[0]=='p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else if(str[0]=='f'){
      scanf("%d",&x);
      fi=find(root,x);
      if(fi==NIL) printf("no\n");
      else printf("yes\n");
    }
    else if(str[0]='d'){
      scanf("%d",&x);
      delete(find(root,x));
    }
  }
  return 0;
}

Measured memory_bytes: 19364
def waru(n,k):
    while(n >= k):
        if(n%k == 0):
            n //= k
        else:
            n %= k
    if(n == 1):
        return 1
    else:
        return 0
n = int(input())
p = 0
if(n < 100):
    for i in range(2,n+1):
        p += waru(n,i)
    print(p)
else:
    for i in range(2,int(n**0.5)+1):
        if(n%i == 1):
            p += 1
        p += waru(n,i)
    if(int((n-1)**0.5)**2 == n-1):
        p -= 1
    print(p+2)

Measured memory_bytes: 3064
//AtCoder ABC090 C - Flip,Flip, and Flip......
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;

int main() {
    ll N,M;
    cin>>N>>M;
    ll ans=0;
    if(N==1&&M==1){
        ans=1;
    }else if(N==1){
        ans=max<ll>(M-2,0);
    }else if(M==1){
        ans=max<ll>(N-2,0);
    }else{
        ans=(N-2)*(M-2);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <string.h>
#include <iostream>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <algorithm>

#define rep(i, n) for (int i = 0; i < n; i++)

const int N = 500;

using namespace std;

int main() {
	int n, c, l = 0, r = 0, min = 109;
	vector<int> v;
	
	cin >> n;
	
	rep(i, n) {
		cin >> c;
		r += c;
		v.push_back(c);
	}
	
	rep(i, n) {
		l += v[i];
		r -= v[i];
		
		min = (min > abs(l - r)) ? abs(l - r) : min;
	}
	
	cout << min << endl;
	
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a) for(int i=0;i<int(a);++i)
#define rrep(i,a) for(int i=int(a)-1; i>=0;--i)
using ll = long long;
using namespace std;
int main(){
    string s;
    cin>>s;
    int ans = 7;
    if(s=="SUN") ans-=0;
    else if(s=="MON") ans-=1;
    else if(s=="TUE") ans-=2;
    else if(s=="WED") ans-=3;
    else if(s=="THU") ans-=4;
    else if(s=="FRI") ans-=5;
    else if(s=="SAT") ans-=6;
    cout<<ans<<endl;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()

#dp = []*n
v = [0]*n
for idt in range(n):
    if idt >= k:
        if t[idt] == t[idt-k] and v[idt-k] != 0:
            v[idt] = 0
            continue
    if t[idt] == 'r':
        v[idt] = p
    elif t[idt] == 's':
        v[idt] = r
    else:
        v[idt] = s
        

ans = sum(v)
print(ans)

Measured memory_bytes: 42096
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  string s;
  cin >> N >> s;
  
  int count1 = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s.at(i) == 'R') {
      count1++;
    }
  }
  
  int count2 = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s.at(i) == 'B') {
      count2++;
    }
  }
  
  if (count1 > count2){
  cout << "Yes" << endl;
  }
  
  else {
  cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>

#include <vector>

#include <stdio.h>

using namespace std;

#define PI 3.141592653589




int main(){

    int n, mark, num;

    char t;

    int c[4][13]={0};

    cin>>n;

    for(int i=0;i<n;i++){

        cin>>t>>num;

        if(t=='S')mark=0;

        if(t=='H')mark=1;

        if(t=='C')mark=2;

        if(t=='D')mark=3;

        c[mark][num-1]=1;

    }

    for(int i=0;i<4;i++){

        for(int j=0;j<13;j++){

            if(c[i][j]==0){

                if(i==0)t='S';

                if(i==1)t='H';

                if(i==2)t='C';

                if(i==3)t='D';

                cout<<t<<" "<<j+1<<endl;

            }

        }

    }

    return 0;

}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define rep(i, n) for(int i=0;i<n;i++)

int main() {
  int n,d;
  cin >> n >> d;
 vector<vector<int>> x(n,vector<int>(d));
  rep(i, n){
    rep(j, d){
      cin >> x.at(i).at(j);
    }
  }
  vector<vector<int>> sum(n,vector<int>(n));
  rep(i,n){
    rep(k,n)
    rep(j,d){
      if(i!=k){
      sum.at(i).at(k)+=(x.at(i).at(j)-x.at(k).at(j))*(x.at(i).at(j)-x.at(k).at(j));
      }
    }
  }
  int sumsum=0;
  rep(i,n){
    rep(k,n)
    if(ceil(sqrt(sum.at(i).at(k)))==floor(sqrt(sum.at(i).at(k)))){
      sumsum++;
    }
  }
   
  
  cout << (sumsum-n)/2 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

signed main() {
    int n;
    cin >> n;
    int ans = INF;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            int a = to_string(i).length();
            int b = to_string(n / i).length();
            int f = max(a, b);
            ans = min(ans, f);
        }
    }
    cout << ans << "\n";
}

Measured memory_bytes: 256
from collections import deque

N, M = map(int,input().split())
count = [0]*N
side = [[]for i in range(N)]
rside = [[]for i in range(N)]

for i in range(N+M-1):
    a,b = map(int,input().split())
    side[a-1].append(b-1)
    rside[b-1].append(a-1)
    count[b-1] += 1
root = count.index(0)
queue = deque([root])
top = [0]*N

for i in range(N):
    q = queue.popleft()
    top[q] = i
    for k in side[q]:
        count[k] -= 1
        if count[k] == 0:
            queue.append(k)
for i in range(N):
    if rside[i] == []:
        print(0)
        continue
    ret = root
    for j in rside[i]:
        if top[ret] < top[j]:
            ret = j
    print(ret+1)


Measured memory_bytes: 82096
#include <iostream>

using namespace std;
int main() {
  int N, a, d = 0, i = 1;
  cin >> N;
  for(int j = 0; j < N; j++)
  {
    cin >> a;
    if(a == i)
    {
      i++;
    }
    else
    {
      d++;
    }
  }
  if(d==N)
  {
    cout << "-1" << endl;
  }
  else
  {
    cout << d << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int n,A[20],q,m;
int a(int i,int m);
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&A[i]);
	scanf("%d",&q);
	for(int i=0;i<q;i++){
		scanf("%d",&m);
		if(a(0,m))
			printf("yes\n");
		else
			printf("no\n");
	}
	return 0;
}
int a(int i,int m){
	if(m==0)
		return 1;
	if(i>=n)
		return 0;
	int b=a(i+1,m)||a(i+1,m-A[i]);
	return b;
}

Measured memory_bytes: 1008
// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define EPS 0.0000000001

class Vector2 {
public:
  double x, y;
  
  Vector2(double x = 0, double y = 0): x(x), y(y) {}
  
  Vector2 operator + (Vector2 v) { return Vector2(x + v.x, y + v.y); }
  Vector2 operator - (Vector2 v) { return Vector2(x - v.x, y - v.y); }
  Vector2 operator * (double k) { return Vector2(x * k, y * k); }
  Vector2 operator / (double k) { return Vector2(x / k, y / k); }
  
  double length() { return sqrt(norm()); }
  double norm() { return x * x + y * y; }
  double dot (Vector2 v) { return x * v.x + y * v.y; }
  double cross (Vector2 v) { return x * v.y - y * v.x; }
  
  bool operator < (const Vector2 &v) const {
    return x != v.x ? x < v.x : y < v.y;
  }
  
  bool operator == (const Vector2 &v) const {
    return fabs(x - v.x) < EPS && fabs(y - v.y) < EPS;
  }
};

ostream & operator << (ostream & out, Vector2 const & v) { 
  out<< "Vector2(" << v.x << ", " << v.y << ')';
  return out;
}

istream & operator >> (istream & in, Vector2 & v) { 
  double x, y;
  in >> x;
  in >> y;
  v.x = x;
  v.y = y;
  return in;
}

#define MAX_M 100000

struct Island {
  Int start, end;
  Island() {}
  Island(Int s, Int e): start(s), end(e) {}
  bool operator < (const Island &v) const {
    return (start == v.start) ? end < v.end : start < v.start;
  }
};

// 1 2 3 4 5 6 7 8 9
// #            |x
//   #        |x
//     #  |x
//       #|  x
//             #  |x
//
// 1 2 3 4 5
// #|x
// #|  x
// #|    x
// #|      x
//   #|x
//   #|  x
//   #|    x
//     #|x
//     #|  x
//       #|x
Int N, M;
vector<Island> is;

void input() {
  cin >> N >> M;
  Int s_, e_;
  loop(m,0,M) {
    cin >> s_ >> e_;
    is.push_back(Island(s_, e_));
  }
}

void solve() {
  sort(span_all(is));
  stack<Island> S;
  Int count = 0, right = -1;
  for (auto i: is) {
    if (right <= i.start) {
      count++;
      right = i.end;
    } else {
      right = min(right, i.end);
    }
  }
  cout << count << endl;
}

int main() {
  input();
  solve();
  return 0;
}


Measured memory_bytes: 1400
#include <stdio.h>

int main(void){
  int num;
  scanf("%d",&num);
  switch(num % 2){
    // Nが偶数の時は半分
    case 0:
      printf("%d",num/2);
      break;
    
    // Nが奇数の時は1足して半分
    case 1:
      printf("%d",(num+1)/2);
      break;
    }
}

Measured memory_bytes: 128
n=1<<18;N,m;L[1<<18],p;first[1<<18],next[1<<18];
long dat[1<<20],lazy[1<<20],A[1<<18];
eval(i,l,r){
	dat[i]+=lazy[i];
	lazy[2*i+1]+=lazy[i];
	lazy[2*i+2]+=lazy[i];
	lazy[i]=0;
}
update(a,b,x,k,l,r)long x;{
	eval(k,l,r);
	if(a<=l&r<=b){
		lazy[k]+=x;
		eval(k,l,r);
	}
	else if(l<b&a<r){
		update(a,b,x,2*k+1,l,(l+r)/2);
		update(a,b,x,2*k+2,(l+r)/2,r);
		dat[k]=fmax(dat[2*k+1],dat[2*k+2]);
	}
}
long query(a,b,k,l,r){
	eval(k,l,r);
	return a<=l&r<=b?dat[k]:l<b&a<r?fmax(
		query(a,b,2*k+1,l,(l+r)/2),
		query(a,b,2*k+2,(l+r)/2,r)
	):0;
}
main(i){
	for(scanf("%d%d",&N,&m);~scanf("%d%d%ld",L+i,&p,A+i);first[p]=i++)next[i]=first[p];
	for(i=1;i<=N;i++){
		update(i,i+1,query(0,i,0,0,n),0,0,n);
		for(p=first[i];p!=0;p=next[p])update(L[p],i+1,A[p],0,0,n);
	}
	printf("%ld",query(0,N+1,0,0,n));
}

Measured memory_bytes: 18944
#include<stdio.h>
#include<stdlib.h>

int compare(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}
int main(void)
{
    int x[3];
    while(1)
    {
        char buffer[256];
        fgets(buffer, 256, stdin);
        sscanf(buffer, "%d %d %d", &x[0], &x[1], &x[2]);
        if((1<=x[0] && x[0]<=10000) &&
        (1<=x[1] && x[1] <= 10000) &&
        (1<=x[2] && x[2] <= 10000)) break;
    }
    qsort(x, 3, sizeof(int), compare);
    printf("%d %d %d\n", x[0], x[1], x[2]);
    
    return(0);
}


Measured memory_bytes: 2036
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
#ifndef LOCAL
#define cerr if(0)cout
#endif
typedef long long ll;
const int mod=1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it, len;
	fastio() {it=len=0;}
	inline char get()
	{
		if (it<len) return s[it++]; it=0;
		len=fread(s, 1, 100000, stdin);
		if (len==0) return EOF; else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while (c==' '||c=='\n') c=get();
		if (it>0) it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0; bool ng=0; char c; c=_buff.get();
	while (c!='-'&&(c<'0'||c>'9')) c=_buff.get();
	if (c=='-') ng=1, c=_buff.get();
	while (c>='0'&&c<='9') r=r*10+c-'0', c=_buff.get();
	return ng?-r:r;
}
template <class T> inline void putnum(T x)
{
	if (x<0) putchar('-'), x=-x;
	register short a[20]={}, sz=0;
	while (x) a[sz++]=x%10, x/=10;
	if(sz==0) putchar('0');
	for (int i=sz-1; i>=0; i--) putchar('0'+a[i]);
}
inline char getreal() {char c=_buff.get(); while (c<=32) c=_buff.get(); return c;}
ll qpow(ll x, ll k) {return k==0? 1: 1ll*qpow(1ll*x*x%mod,k>>1)*(k&1?x:1)%mod;}
int id[2011], n;
int main()
{
	int K;
	cin>>K;
	while (n*2<K||n%2==1) n++;
	for (int i=0; i<n+n; i++) id[i] = K==1?0:(i<K?i:i-n);
	putsi(n);
	for (int i=0; i<n; i++)
	{
		for (int j=0; j<n; j++)
		{
			puti(id[(i+j)%n+(i&1)*n]+1);
		}
		puts("");
	}
	return 0;
}


Measured memory_bytes: 1152
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		while(true){
			int n=sc.nextInt();
			if(n==0)break;
			ArrayList <Integer> temp=new ArrayList<Integer>();
			for(int i=0;i<n;i++){
			temp.add(sc.nextInt());
			
			}
			
			
			
			
			
			Collections.sort(temp);
			temp.remove(0);
			temp.remove(temp.size()-1);
			System.out.println(ans(temp));
		}
	}
	
	
	
	
	
	
	
	public static int ans(ArrayList<Integer> List){
		int sum=0;
		int temp=0;
		for(int i=0;i<List.size();i++){
			sum+=List.get(i);
		}
		temp=sum/List.size();
		return temp;
		
		
	
	}
}

Measured memory_bytes: 20988
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> T;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
int n;
int p[105];
P dp[105][100000];
P dfs(int id,int ch){
	if(id==n){
		return P(0,0);
	}
	int rem = p[id]%1000;
	if(dp[id][ch].fi!=-1)return dp[id][ch];
	P res = dfs(id+1,ch);
	if(rem==0){
		if(ch>=500){
			P tmp = dfs(id+1,ch-500);
			tmp.fi++;
			tmp.sec-=p[id];
			res = max(res,tmp);
		}
	}else{
		if(ch+500-rem>=0){
			P tmp = dfs(id+1,ch+500-rem);
			tmp.fi++;
			tmp.sec -= p[id];
			res = max(res,tmp);
		}
		P tmp = dfs(id+1,ch+1000-rem);
		tmp.sec -= p[id];
		res = max(res,tmp);
	}
	return dp[id][ch]=res;
}
bool solve(){
	cin >> n;
	if(n==0)return false;
	for(int i=0;i<n;i++){
		cin >> p[i];
	}
	for(int i=0;i<105;i++){
		for(int j=0;j<100000;j++){
			dp[i][j]=P(-1,-1);
		}
	}
	P ans = dfs(0,0);
	cout << ans.fi << ' ' << -ans.sec << endl;
	return true;
}
int main(){
	while(solve()){}
	return 0;
}



Measured memory_bytes: 85028
from itertools import accumulate

def getDivisor(x):
    ans = []
    for d in range(1, int(x**0.5)+1):
        if x%d == 0:
            ans.append(d)
            if x//d != d:
                ans.append(x//d)
    return sorted(ans)


N, K = map(int, input().split())
As = list(map(int, input().split()))

sumA = sum(As)
divisors = getDivisor(sumA)

def f(d):
    Bs = [A%d for A in As]
    Bs.sort()
    sumB = sum(Bs)
    accBs = list(accumulate(Bs))
    for i in range(1, N):
        numSub = accBs[i-1]
        numAdd = d*(N-i) - (sumB-accBs[i-1])
        if numSub <= K and numAdd <= K and (numSub-numAdd)%d == 0:
            return True
    return False


for d in reversed(divisors):
    ret = f(d)
    if ret:
        print(d)
        break
else:
    print(1)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
void Main();

using i8  = int8_t;   /* -128 ~ 127 */
using u8  = uint8_t;  /* 0 ~ 255 */
using i16 = int16_t;  /* -32,768 ~ 32,767 */
using u16 = uint16_t; /* 0 ~ 65,535 */
using i32 = int32_t;  /* -2,147,483,648 ~ 2,147,483,647 */
using u32 = uint32_t; /* 0 ~ 4,294,967,295 */
using i64 = int64_t;  /* -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 */
using u64 = uint64_t; /* 0 ~ 18,446,744,073,709,551,615 */
using f32 = float;    /* (-3.4 * 10^38) ~ (3.4 * 10^38) */
using f64 = double;   /* (-1.7 * 10^308) ~ (1.7 * 10^308) */
using f80 = __float80;
template <class T> using Vec = vector<T>;
constexpr i64 INF = 1010000000000000017;
constexpr i64 MOD = 1e9 + 7;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#define ALL(v) v.begin(), v.end()
#define GCD(a, b) __gcd(a, b) /* 最大公約数 */
#define LCM(a, b) a / __gcd(a, b) * b /* 最小公倍数 */

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}

void Main() {
    u32 N, M;
    cin >> N >> M;
    if (N == M) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
import java.util.*;
import java.util.stream.*;

public class Main {
	Scanner sc;
	int N, NN;
	Integer[] S;
	TreeSet<Slime> slimes;
	Slime[] indices;
	Comparator<Slime> order;
	
	static class Slime {
		int id, val;
		Slime(int id) {
			this.id = id;
		}
	}
	
	public Main() {
		sc = new Scanner(System.in);
		order = Comparator.comparingInt( (Slime s) -> (0x7fffffff & (-lsb(s.id))) ).
				thenComparingInt( s -> countOnes(s.id) ).
				thenComparingInt( s -> s.id );
	}
	
	private void calc() {
		N = sc.nextInt();
		NN = 1<<N;
		S = new Integer[NN];
		for (int i = 0; i < NN; i++) S[i] = sc.nextInt();
		Arrays.sort(S, Comparator.reverseOrder());
		slimes = new TreeSet<Slime>(order);
		indices = new Slime[NN];
		for (int i = 0; i < NN; i++) indices[i] = new Slime(i);
		slimes.add(indices[0]);
		indices[0].id = NN;
		Iterator<Slime> it = null;
		int lasts = Integer.MAX_VALUE;
		List<Slime> next = new ArrayList<>();
	lp:
		for (int j = 0; j < NN; j++) {
			if (lasts != S[j]) {
				slimes.addAll(next);
				next.clear();
				it = slimes.iterator();
			}
			while (it.hasNext()) {
				Slime s = it.next();
				if (j == 0 || indices[s.id ^ lsb(s.id)].val > S[j]) {
					s.val = S[j];
					it.remove();
					lasts = S[j];
					for (int l = (lsb(s.id) >>> 1); l > 0; l = l >>> 1)
						next.add(indices[(s.id | l)&(NN-1)]);
					continue lp;
				}
			}
			System.out.println("No");
			return;
		}
		System.out.println("Yes");
	}
	
	static int countOnes(int t) {
		t = (t & 0x55555555) + (t >> 1 & 0x55555555);
		t = (t & 0x33333333) + (t >> 2 & 0x33333333);
		t = (t & 0x0f0f0f0f) + (t >> 4 & 0x0f0f0f0f);
		t = (t & 0x00ff00ff) + (t >> 8 & 0x00ff00ff);
		return (t & 0x0000ffff) + (t >>16 & 0x0000ffff);
	}
	
	static int lsb(int t) {
		return t&(-t);
	}
	public static void main(String[] args) {
		new Main().calc();
	}
}



Measured memory_bytes: 112948
#include <cmath>
#include <iostream>
using namespace std;

int main()
{
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if (abs(c - a) <= d)
    cout << "Yes";
  else if ((abs(b - a) <= d) && (abs(c - b) <= d))
    cout << "Yes";
  else
    cout << "No";
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef array<ll,2> pll;
const ll NMAX=3005;
ll dp[NMAX][NMAX];
int main()
{
    string a,b;
    cin>>a>>b;
    for(ll i=0;i<a.size();i++){
        for(ll j=0;j<b.size();j++){
            ll cnd=max(dp[i][j+1],dp[i+1][j]);
            if(a[i]==b[j]) cnd=max(cnd,dp[i][j]+1);
            dp[i+1][j+1]=cnd;
        }
    }
    ll x=a.size(),y=b.size();
    string ans;
    while(x>0 && y>0){
        if(a[x-1]==b[y-1]){
            ans.push_back(a[x-1]);
            x--; y--;
        }
        else if(dp[x-1][y]>dp[x][y-1])
            x--;
        else y--;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans;
    return 0;
}


Measured memory_bytes: 74000
//#include "bits/stdc++.h"

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, double> pid;
typedef pair<double, int> pdi;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int f(int b, int n)
{
	if (n < b)return n;
	return f(b, n / b) + n % b;
}

signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N, S;
	cin >> N >> S;

	if (N == S)
	{
		cout << N + 1 << endl;
		return 0;
	}

	rep(i, 2, (int)sqrt(N) + 1)
	{
		if (f(i, N) == S)
		{
			cout << i << endl;
			return 0;
		}
	}

	if (N > S)
	{
		rrep(i, 1, (int)sqrt(N)+1)
		{
			if ((N - S) % i == 0 && f((N - S) / i + 1, N) == S)
			{
				cout << (N - S) / i + 1 << endl;
				return 0;
			}
		}
	}

	cout << -1 << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <utility>
#include <map>
#define ll long long
using namespace std;
#include<bits/stdc++.h>
using namespace std;

int main(void){
    ll n;
    ll inf = 1e9+7;
    cin >> n;
    string s;
    cin >> s;
    vector<ll> check(26, 0);
    for(ll i = 0; i < s.length(); i++){
        ll array = s[i]-97;
        check[array]++;
    }
    ll ans = 1;
    for(ll i = 0; i < 26; i++){
        ans = ans * (check[i]+1)%inf;
        ans %= inf;
    }
    cout << ans-1 << endl;
    return 0;
}


Measured memory_bytes: 512
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int K = scanner.nextInt();
    int x = scanner.nextInt();
    int y = scanner.nextInt();
    int sx = 1, sy = 1;
    if (x < 0) {
      sx = -1;
      x = -x;
    }
    if (y < 0) {
      sy = -1;
      y = -y;
    }
    List<Diff> diffs = new ArrayList<>();

    while (x + y > K * 2) {
      int dx, dy;
      if (y > K) {
        dx = 0;
        dy = -K;
      } else {
        dx = -K;
        dy = 0;
      }
      diffs.add(new Diff(dx, dy));
      x += dx;
      y += dy;
    }

    if (K % 2 == 0 && (x + y) % 2 != 0) {
      System.out.println(-1);
      return;
    }
    if (x + y == K) {
      System.out.println(1);
      System.out.printf("%d %d\n", sx * x, sy * y);
      return;
    }
    if (K % 2 != 0 && (x + y) % 2 != 0) {
      int dx, dy;
      if (x + y > K) {
        dy = -Math.min(y, K);
        dx = y + dy == 0 ? -(K - y) : 0;
      } else {
        dy = 0;
        dx = K;
      }
      diffs.add(new Diff(dx, dy));
      x += dx;
      y += dy;
    }

    int p, q;
    if (x > y) {
      p = (x - y) / 2;
      q = K - p;
    } else {
      q = (y - x) / 2;
      p = K - q;
    }
    diffs.add(new Diff(p - x, q - y));
    diffs.add(new Diff(-p, -q));

    Collections.reverse(diffs);
    long xx = 0;
    long yy = 0;
    StringBuilder sb = new StringBuilder();
    sb.append(diffs.size()).append('\n');
    for (Diff d : diffs) {
      xx += -sx * d.x;
      yy += -sy * d.y;
      sb.append(xx).append(' ').append(yy).append('\n');
    }
    System.out.print(sb.toString());
  }

  private static class Diff {
    private final int x;
    private final int y;

    private Diff(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }
}


Measured memory_bytes: 46968
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
template<typename T>
class ConvexHullTrick {
private:
	vector<pair<T, T>> lines;
public:
	ConvexHullTrick() {
		lines.emplace_back(0, 0);
	}
	bool check(pair<T, T> l1, pair<T, T> l2, pair<T, T> l3) {
		if (l1 < l3) swap(l1, l3);
		return (l3.second - l2.second)*(l2.first - l1.first) >= (l2.second - l1.second)*(l3.first - l2.first);
	}
	void add(T a, T b) {
		pair<T, T> line(a, b);
		while (lines.size() >= 2 && check(*(lines.end() - 2), lines.back(), line)) lines.pop_back();
		lines.push_back(line);
	}
	T f(int i, T x) {
		return lines[i].first*x + lines[i].second;
	}
	T get(T x) {
		int low = -1, high = lines.size() - 1;
		while (high - low > 1) {
			int mid = (high + low) / 2;
			if (f(mid, x) < f(mid + 1, x)) high = mid;
			else low = mid;
		}
		return f(high, x);
	}
};
ll h[200000];
ll dp[200000];
int main() {
	int N;
	ll C;
	cin >> N >> C;
	for (int i = 0; i < N; i++) {
		cin >> h[i];
	}
	ConvexHullTrick<ll> cht;
	cht.add(-2 * h[0], h[0] * h[0]);
	for (int i = 1; i < N; i++) {
		dp[i] = h[i] * h[i] + C + cht.get(h[i]);
		cht.add(-2 * h[i], dp[i] + h[i] * h[i]);
	}
	cout << dp[N - 1] << endl;
}

Measured memory_bytes: 9328
#include <bits/stdc++.h>

using namespace std;

int main() {
    string s[3];
    int id[3] = { 0 }, next = 0;

    for (int i = 0; i < 3; ++i) {
        cin >> s[i];
    }
    while (id[next] < s[next].size()) {
        next = s[next][id[next]++] - 'a';
    }
    cout << char(next + 'A') << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;
using ll =long long;
typedef pair<int,int> P;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//Write From this Line

int main()
{
	ll n, c;
	cin >> n >> c;
	vector<ll> x(n), v(n);
	rep(i,n) cin >> x[i] >> v[i];

	// 左回りに取っていった時の累積
	vector<ll> left(n+1);
	ll pos = 0;
	left[0] = 0;
	rep(i,n){
		left[i+1] = left[i] + v[i] - (x[i] - pos);
		pos = x[i];
	}
	vector<ll> right(n+1);
	right[0] = 0;
	pos = c;
	rep(i,n){
		right[i+1] = right[i] + v[n-i-1] - abs(x[n-i-1] - pos);
		pos = x[n-i-1];
	}

	// 左から i 個取れるときの最大
	vector<ll> max_left(n+1);
	rep(i,n+1){
		max_left[i] = left[i];
		if(i != 0) chmax(max_left[i], max_left[i-1]);
	}
	vector<ll> max_right(n+1);
	rep(i,n+1){
		max_right[i] = right[i];
		if(i != 0) chmax(max_right[i], max_right[i-1]);
	}

	ll ans = 0;
	rep(i,n+1){
		// 左からi個食べる
		ll tmp = left[i];
		chmax(ans,tmp);
		if(i == n) // 全部食った
		{
			continue;
		}
		else
		{
			// 右から n - i 個食える
			if(i != 0){
				// 0 まで戻ってくる
				tmp -= x[i-1];
			}
			tmp += max_right[n-i];
			chmax(ans,tmp);
		}
	}
	rep(i,n+1){
		// rightからi個食べる
		ll tmp = right[i];
		chmax(ans,tmp);
		if(i == n) // 全部食った
		{
			continue;
		}
		else
		{
			// 右から n - i 個食える
			if(i != 0){
				// i = 1 なら x[n-1];
				tmp -= (c-x[n-i]);
			}
			tmp += max_left[n-i];
			chmax(ans,tmp);
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 8024
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Int int32_t
#define all(c) c.begin(), c.end()
#define FAST ios_base::sync_with_stdio(false) , cin.tie(NULL);
#define pii pair< int , int >
#define pb push_back
#define F first
#define S second
#define endl "\n"
#define bitcnt(n) __builtin_popcountll(n)
#define setpre(n) cout << fixed << setprecision(n)
#define tr(c) for(auto x : c )cout << x << " ";
#define ol(c , s , e ) for(int pos=s; pos<e ; pos++) cout << c[pos] << " ";
#define PI acos(-1l)
const int M = 1000000007;
const int N=3e5+5;
const int INF = 2e18+5;
//#define rohit
#ifdef rohit
template<typename... T >
void bug(T... __VA_ARGS__) {
    ((cerr << __VA_ARGS__ << " ") , ...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", bug(__VA_ARGS__) , cerr << endl;
#endif

void solve(){
    int a , b , v, w ,t;
    cin >> a >> v;
    cin >> b >> w;
    cin >> t;
    if(w >= v ){
        cout << "NO";
        return;
    }
    if(a < b){
        b = b + t*w;
        a = a + t*v;
        if(a >= b ){
            cout<<"YES";
        }
        else{
            cout <<"NO";
        }
    }
    else{
        b = b - t*w;
        a = a - t*v;
        if(a <= b ){
            cout <<"YES";
        }
        else{
            cout <<"NO";
        }
    }
}

signed main(){
    FAST;
    //TODO: check test cases.
    int tc=1;
//    cin >> tc;
    for(int t = 1 ; t <= tc ; t++){
        solve();
    }
}
/* Extra Cares
 * 1)In graphs or dp problems sometimes long long creates MLE.
 * 2)Check whether int to long long typecasting is commented or not?
 * 3)Check overflows.
*/



Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define ins insert
#define eb emplace_back
#define endl '\n'
#define ll long long
#define ld long double
#define vl vector<ll>
#define no cout << "No" << endl
#define yes cout << "Yes" << endl
#define tc ll t; cin >> t; while (t--)
#define sz(c) (ll) (c).size()
#define trav(x,c) for(auto &x : c)
#define all(c) (c).begin(), (c).end()
#define rll(c) (c).rbegin(), (c).rend()
#define _for(i,a,n) for(ll i = a ; i < n; ++i)
#define _rfor(i,a,n) for(ll i = n-1 ; i >= a; --i)
#define dx(x) cout << #x << ": " << x << endl;
#define dc(c) trav(x,c) cout << x << " "; cout << endl;
#define godspeed ios::sync_with_stdio(0); cin.tie(0);

ll f(ll n) {
    if(n == 1) return 1;
    return 2*(f(floor(n/2))) + 1; 
}

int main() {
    godspeed;
    ll n; cin >> n;
    cout << f(n);
}

Measured memory_bytes: 3624
#include<stdio.h>

struct Node {
	//root検出用の変数
	int p;
	int left, right;
};
struct Node T[10000];

void PreParse(int i) {
	if (i == -1) {
		return;
	}
	printf(" %d", i);
	PreParse(T[i].left);
	PreParse(T[i].right);
}

void InParse(int i) {
	if (i == -1) {
		return;
	}
	InParse(T[i].left);
	printf(" %d", i);
	InParse(T[i].right);
}

void PostParse(int i) {
	if (i == -1) {
		return;
	}
	PostParse(T[i].left);
	PostParse(T[i].right);
	printf(" %d", i);
}

int main(void){
	int i, n, value, left, right, root;

	scanf("%d", &n);
	//初期化
	for (i = 0; i < n; i++) {
		T[i].p = -1;
	}

	//rootの検出
	for (i = 0; i < n; i++) {
		scanf("%d %d %d", &value, &left, &right);
		T[value].left = left;
		T[value].right = right;

		//ある点からの到着点にならないノードがroot
		if (left != -1) {
			T[left].p = 1;
		}
		if (right != -1) {
			T[right].p = 1;
		}
	}

	for (i = 0; i < n; i++) {
		//「到着点として」存在しないノードがroot
		if (T[i].p == -1) {
			root = i;
		}
	}

	printf("Preorder\n");
	PreParse(root);
	putchar('\n');
	printf("Inorder\n");
	InParse(root);
	putchar('\n');
	printf("Postorder\n");
	PostParse(root);
	putchar('\n');

	return 0;
}



Measured memory_bytes: 2052
N = int(input())
A = list(map(int, input().split()))

#SA = []
#for i in range(N):
#    SA.append(A[i], i)
#SA.sort(reverse=True)

# A[i] = ans[i]/2 + ans[i+1]/2
ans = [0] * N

# A[i] = ans[i]/2 + ans[i+1]/2
# ans[i] =  2A[i] - ans[i+1]
# A[i+1] = ans[i+1]/2 + ans[i+2]/2
# ans[i+1] =  2A[i+1] - ans[i+2]
for i in range(N):
    if i%2 == 0:
        tmp = -1
    else:
        tmp = 1
    tmp *= A[i] * 2
    ans[0] -= tmp
ans[0] //= 2

for i in range(1, N):
    ans[-i] = A[-i] * 2 - ans[-i+1]

print(' '.join(map(str, ans)))
#for i in range(ans)


Measured memory_bytes: 84580
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

class DisjointSet {
    public:
        vector<int> rank, p;
    
    DisjointSet() {}
    DisjointSet(int size) {
        rank.resize(size, 0);
        p.resize(size, 0);
        rep(i,size) makeSet(i);
    }

    void makeSet(int x) {
        p[x] = x;
        rank[x] = 0;
    }

    bool same(int x, int y) {
        return findSet(x) == findSet(y);
    }
    void unite(int x, int y) {
        link(findSet(x), findSet(y));
    }

    void link(int x, int y) {
        if (rank[x] > rank[y]) {
            p[y] = x;
        } else {
            p[x] = y;
            if (rank[x] == rank[y]) {
                rank[y]++;
            }
        }
    }

    int findSet(int x) {
        if ( x != p[x] ) {
            p[x] = findSet(p[x]);
        }
        return p[x];
    }
};



int main(){
    int n, a, b, q;
    int t;
    cin >> n>> q;
    DisjointSet ds = DisjointSet(n);
    rep(i,q) {
        cin >> t >> a >> b;
        if (t == 0) ds.unite(a,b); 
        else if ( t == 1 ) {
            if (ds.same(a,b)) cout << 1 << endl;
            else cout << 0 << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3188
while True:
    a, op, b = raw_input().split()
    ai = int(a)
    bi = int(b)
    if op == '?':
        break
    elif op == '+':
        print(ai + bi)
    elif op == '-':
        print(ai - bi)
    elif op == '*':
        print(ai * bi)
    elif op == '/':
        print(ai / bi)

Measured memory_bytes: 6436
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


namespace{
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}


#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8
static const int INF=1<<24;
int dp[(1<<15)+1];
void mainmain(){
	int n=1<<15;
	n++;
	for(int i=0;i*i<n+1;i++){
		for(int j=i;j*j+i*i<n+1;j++){
			for(int k=j;k*k+j*j+i*i<n+1;k++){
				for(int l=k;l*l+k*k+j*j+i*i<n+1;l++){
					dp[l*l+k*k+j*j+i*i]++;
				}
			}
		}
	}
	while(cin>>n,n){
		cout<<dp[n]<<endl;
	}
}



}
main() try{
    mainmain();
}
catch(...){
}

Measured memory_bytes: 1288
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
 
    ll n;
    cin>>n;
    pair<int,int> p[n];
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        p[i] = make_pair(a,i);
    }
    int ans[n]={};
    sort(p,p+n);
    for(int i=0;i<n;i++){
        ans[i] = p[i].second;
    }
    for(int i=0;i<n;i++){
        cout << ans[i]+1 << " ";
    }
    cout << endl;

}

Measured memory_bytes: 2048