akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;

int N, M, K;
long long fact[200005];
long long ans;

long long POW(long long X, long long Y) {
  long long res = 1;
  while(Y) {
    if(Y & 1) res = res * X % MOD;
    X = X * X % MOD;
    Y >>= 1;
  }
  return res;
}

long long moddiv(long long A, long long B) {
  return A * POW(B, MOD - 2) % MOD;
}

int main() {
  scanf("%d %d %d", &N, &M, &K);
  fact[0] = 1;
  for(int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
  for(int i = N - K; i <= N; i++) {
//    cout << i << " " << M * POW(M - 1, i - 1) % MOD * moddiv(fact[N - 1], fact[N - i] * fact[i - 1] % MOD) % MOD << "\n";
    ans += M * POW(M - 1, i - 1) % MOD * moddiv(fact[N - 1], fact[N - i] * fact[i - 1] % MOD) % MOD;
  }
  printf("%lld\n", ans % MOD);
}

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

int main(){
  string S;
  cin >> S;
  int A=S.size();
  bool a=false;
  for(int i=0;i<A-1;i++){
    if(S.at(i)=='C'){
      for(int j=i+1;j<A;j++){
        if(S.at(j)=='F'){
          a=true;
          break;
        }
      }
      if(a){
        break;
      }
    }
  }
  if(a){
    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)
using namespace std;
using ll =long long;
using P =pair<int,int>;

int main(){
    int h,w;
    cin >> h >> w;
    int a,c;
    vector <int> b(h*w),b2(h*w);
    rep(i,h*w){
        cin >> b[i];
    }

    b2=b;

    rep(i,h){
        if(i%2==1){
            rep(j,w){
                b2[i*w+j]=b[i*w+w-j-1];
            }
        }
    }

    vector <int> ans(h*w,0),ans2(h*w,0);
    int k=0;

    rep(i,h*w){
        if(b2[i]%2==1 and i!=h*w-1){
            ++b2[i+1];
            ans[i]=1;
            ++k;
        }
    }
    ans2=ans;

    rep(i,h){
        if(i%2==1){
            rep(j,w){
                ans2[i*w+j]=ans[i*w+w-j-1];
            }
        }
    }

    vector <int> y1(k),y2(k),y3(k),y4(k);
    int k2=0;
    rep(i,h){
            rep(j,w){

                if(ans2[i*w+j]==1){
                    y1[k2]=i;
                    y2[k2]=j;
                    
                    if(i%2==0){
                        if(j==0){
                            if(w==1){
                                y3[k2]=i+1;
                                y4[k2]=j;
                            }
                            else{
                            y3[k2]=i;
                            y4[k2]=j+1;
                            }
                        }
                        else if(j==w-1){
                            y3[k2]=i+1;
                            y4[k2]=j;
                        }
                        else{
                            y3[k2]=i;
                            y4[k2]=j+1;
                        }
                    }
                    else{
                        if(j==0){
                            y3[k2]=i+1;
                            y4[k2]=j;
                        }
                        
                        else{
                            y3[k2]=i;
                            y4[k2]=j-1;
                        
                    }
                }
                ++k2;
            }
        }
    }

    cout << k << endl;
    
    rep(i,k){
        cout << y1[i]+1 << " " << y2[i]+1 << " " << y3[i]+1 << " " << y4[i]+1 << endl;
    }

    return 0;
}

Measured memory_bytes: 7936
H, W = map(int, input().split())
answer = 10**6
if H%3 == 0 or W%3 == 0:
  print(0)
else:
  # h 1 w 2
  S = H*W
  s1 = s2 = s3 = 0
  for h in range(1, H):
    s1 = h*W
    s2 = (H-h)*(W//2)
    s3 = S-s1-s2
    answer = min(answer, max(s1, s2, s3)-min(s1, s2, s3))
    s2 = ((H-h)//2)*W
    s3 = S-s1-s2
    answer = min(answer, max(s1, s2, s3)-min(s1, s2, s3))
  for w in range(1, W):
    s1 = w*H
    s2 = (W-w)*(H//2)
    s3 = S-s1-s2
    answer = min(answer, max(s1, s2, s3)-min(s1, s2, s3))
    s2 = ((W-w)//2)*H
    s3 = S-s1-s2
    answer = min(answer, max(s1, s2, s3)-min(s1, s2, s3))
  print(answer)

Measured memory_bytes: 73572
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<map>
#include<cmath>
#include<cstring>
#include<iomanip>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
#define INF = 1000000100;
#define rep(i,n) for (int i=0;i<n;i++)

const int M=1000005;

int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i,N) cin >> a[i];
    vector<int> cnt(M);
    for(int x: a){
        if(cnt[x]!=0){
            cnt[x] = 2;
            continue;
        }
        for(int i=x;i<M;i+=x){
            cnt[i]++;
        }
    }
    int ans =0;
    for(int x : a){
        if(cnt[x]==1) ans++;
    }
    cout << ans << endl;
    return 0;

}

Measured memory_bytes: 7632
#include <bits/stdc++.h>
#define mxn (int)1e5+10
using namespace std;

int ar[mxn], dp[mxn];

int solve(int n) {
    if(n == 0) return 0;
    if(n == 1) return abs(ar[1] - ar[0]);

    if(dp[n] != -1)  return dp[n];

    int s1 = solve(n-1);
    int s2 = solve(n-2);

    return dp[n] = min(s1 + abs(ar[n] - ar[n-1]), s2 + abs(ar[n] - ar[n-2]));
}

int main() {
    int n; cin >> n;
    for(int i=0; i<n; ++i) cin >> ar[i];
    for(int i=0; i<mxn; ++i) dp[i] = -1;

    cout << solve(n-1) << '\n';

    return 0;
}


Measured memory_bytes: 5760
//shara's here
#include<bits/stdc++.h>
using namespace std;
int main(){
	string x,y,z;
	cin>>x>>y>>z;
	int lenx=x.size()-1;
	int leny=y.size()-1;
	int lenz=z.size()-1;
	if(x[lenx]==y[0]&&y[leny]==z[0]){cout<<"YES";}
	else cout<<"NO";
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true) {
			int a = sc.nextInt();
			String op = sc.next();
			int b = sc.nextInt();
			
			if(op.equals("?")){
				break;
			}
			else if(op.equals("+")) {
				System.out.println(a + b);
			}
			else if(op.equals("-")) {
				System.out.println(a - b);
			}
			else if(op.equals("*")) {
				System.out.println(a * b);
			}
			else {
				System.out.println(a / b);
			}
		}
	}

}



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

typedef long long int int64;

void bsort(int *a,int n,int *bucket,int sup){
  int i;
  for(i=0;i<n;i++) bucket[a[i]]++;
  int j=0;
  for(i=0;i<sup;i++){
    while(bucket[i]>0){
      a[j++]=i;
      bucket[i]--;
    }
  }
  return;
}

int cmp(const void *a,const void *b){
  return *(int *)a-*(int *)b;
}

//a+b>=v 
int64 calc(int *a,int *b,int n,int v){
  int i=0;
  int j=n-1;
  while(i<n && a[i]+b[j]<v) i++;
  int64 cnt=0;
  for(;i<n;i++){
    while(j>=0 && a[i]+b[j]>=v) j--;
    cnt+=n-1-j;
  }
  return cnt;
}

void run(void){
  const int c=20;
  int n;
  scanf("%d",&n);
  int *a=(int *)malloc(sizeof(int)*n);
  int *b=(int *)malloc(sizeof(int)*n);
  int *bucket=(int *)calloc(1<<c,sizeof(int));
  int i;
  for(i=0;i<n;i++) scanf("%d",a+i);
  for(i=0;i<n;i++) scanf("%d",b+i);
  int ans=0;
  int bit;
  for(bit=29;bit>=0;bit--){
    for(i=0;i<n;i++) a[i]=a[i]&((1<<(bit+1))-1);
    for(i=0;i<n;i++) b[i]=b[i]&((1<<(bit+1))-1);
    if(bit+1<=c){
      bsort(a,n,bucket,1<<(bit+1));
      bsort(b,n,bucket,1<<(bit+1));
    } else {
      qsort(a,n,sizeof(int),cmp);
      qsort(b,n,sizeof(int),cmp);
    }
    int64 cnt=(calc(a,b,n,1<<bit)-calc(a,b,n,2*(1<<bit))+calc(a,b,n,3*(1<<bit)));
    if(cnt%2) ans+=1<<bit;
  }
  printf("%d\n",ans);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 6636
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define repone(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define Rep(j,n) for(int j=0;j<(int)(n);++j)
#define Repo(j,o,n) for(int j=o;j<(int)(n);++j)
#define Repone(j,n) for(int j=1;j<(int)(n);++j)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define int long long
#define pb(a) push_back(a)
#define eraser(v,i) (v).erase(v.begin()+(i))
#define pbpair(a,b) push_back(make_pair(a,b))
#define MOD 1000000007
#define INF 9223372036854775807
#define pairint pair<int,int>
signed main()
{
int x=0,y=0,z=0,w=0,n=0,m=0,a=0,b=0;
std::vector<int> v(5);
rep(i,5){
  std::cin >> v[i];
  if(v[i]%10>0){
    y=10-v[i]%10;
    if(i==0)x=y;
    else if(x<y)x=y;
    v[i]+=y;
  }
  z+=v[i];
}
std::cout << z-x << '\n';
return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args)throws Exception{
		Scanner stdIn=new Scanner(System.in);
		long N=stdIn.nextLong();
		long A=stdIn.nextLong();
		long B=stdIn.nextLong()+A;
		long C=0;
		C=N/B;
		N-=C*B;
		if(A>=N)
			System.out.println(C*A+N);
		else
			System.out.println(C*A+A);
	}
}


Measured memory_bytes: 23764
import math

while 1:
    n, l, r = map(int, input().split())
    if (n, l, r) == (0, 0, 0): break
    aa = [int(input()) for _ in range(n)]
    koho = set([i for i in range(l, r + 1)])
    baisu = set()
    uru = set()
    for i, a in enumerate(aa):
        start = math.ceil(l / a) * a
        for k in range(start, r + 1, a):
            baisu.add(k)
        # iが奇数の時＝うるう
        if not i % 2:
            uru |= koho & baisu
        koho -= baisu
    if not n % 2:
        uru |= koho
    print(len(uru))



Measured memory_bytes: 6432
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
AB = list(list(map(int,readline().split())) for _ in range(N-1))
M = int(readline())
UV = list(list(map(int,readline().split())) for _ in range(M))

graph = [[] for _ in range(N+1)]
for i, (a,b) in enumerate(AB):
    graph[a].append((b,i))
    graph[b].append((a,i))

def get_path(U,V):
    INF = 100
    visited = [False] * (N+1)
    pred = [None] * (N+1)
    stack = [U]
    visited[U] = True
    while stack:
        v = stack.pop()
        for w, i in graph[v]:
            if visited[w]:
                continue
            visited[w] = True
            pred[w] = (v,i)
            stack.append(w)
    path = 0
    w = V
    while w != U:
        v,i = pred[w]
        w = v
        path += 1<<i
    return path

condition_path = [get_path(u,v) for u,v in UV]

S = np.zeros(1<<M,np.int64)
sgn = np.ones(1<<M,np.int64)
for i in range(M):
    S[1<<i:1<<(i+1)] = S[:1<<i] | condition_path[i]
    sgn[1<<i:1<<(i+1)] = -sgn[:1<<i]

def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

n_edges = popcnt(S)

x = 1<<(N-1-n_edges)
answer = (x * sgn).sum()
print(answer)

Measured memory_bytes: 61600
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import random
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


S = sys.stdin.buffer.readline().decode().rstrip()
ok=False
for i in range(1,6):
    ok  |= S == 'hi' * i
if ok:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 24184
#include <iostream>
#include <algorithm>
using namespace std;
int n,a[61],k,ans=0;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=n;i>n-k;i--)
	ans+=a[i];
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
import collections

n = int(input())
s = []
for i in range(n):
    s.append(input())
m = int(input())
t = []
for i in range(m):
    t.append(input())

for i in range(len(t)):
    for j in range(len(s)):
        if t[i] == s[j]:
            del s[j]
            break

d = collections.defaultdict(int)

for c in s:
    d[c] += 1

if len(d) == 0:
    print(0)
else:
    print(max(d.values()))

Measured memory_bytes: 3316
#include <vector>
#include <iostream>
using namespace std;

vector<int> adj[2000];

int dfs(int i, int k, int p=-1) {
    int ans = 0;
    for (int j : adj[i]) if (j != p) ans += dfs(j, k-1, i);
    return ans + (k < 0 ? 1 : 0);
}

int main() {
    int n, k; cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int ans = n;
    for (int i = 0; i < n; i++) {
        int sum = dfs(i, k/2);
        ans = min(ans, sum);

        if (k % 2) {
            for (int j : adj[i]) {
                ans = min(ans, sum + dfs(j, (k+1)/2-1, i) - dfs(j, k/2-1, i));
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 512
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int count;
		
		if(n % 2 == 0) {
			count = (n / 2) * (n / 2);
		}else {
			count = (n / 2) * (n / 2 + 1);
		}
		
		System.out.println(count);
	}
}


Measured memory_bytes: 21332
#include <iostream>
using namespace std;
int main (){
 int s[13]={2,3,4,5,6,7,8,9,10,11,12,13,1};
 int a,b;

   cin>>a>>b;
   int f=0,t=0;
   for (int i=0;i<13;i++){
   if (a==s[i])
   f=i;
    if(b==s[i])
   t=i;


   }
   if (f>t)
    cout <<"Alice"<<endl;
   else if (f<t)
    cout<<"Bob"<<endl;
   else
    cout <<"Draw"<<endl;


return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fir first
#define sec second
#define pb 	push_back
#define ll  long long
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define debug(x) cerr<<#x<<" =: "<<x<<endl;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define Find find_by_order
#define Order order_of_key
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
mt19937 mrand(random_device{}());
ll rnd(ll x) { return mrand() % x;}
ll ksm(ll a,ll b,ll mod){ll ans=1;a%=mod;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;}
ll phi(ll n){ll ans=n;for(ll i=2;i*i<=n;i++){if(n%i==0) {while(n%i==0) n/=i;ans=ans*(i-1)/i;}}if(n>1) ans=ans*(n-1)/n;return ans;}
//head

const int maxn = 1e6 + 7;
vector<int> vec[maxn];
int a[maxn], ans[maxn];
set<int> s;

int main (){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if ((c / b + ((c % b) > 0)) <= (a / d + ((a % d)>0))) cout << "Yes" << endl;
    else cout << "No" <<endl;
    return 0;
}


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

int main()
{
	
	int h,w;
	cin>>h>>w;
	string str[105];
	for(int i=0;i<h;i++)
	{
		cin>>str[i];
	}
	for(int i=0;i<w+2;i++)
	{
		cout<<"#";
	}
	cout<<endl;
	for(int i=0;i<h;i++)
	{
		cout<<"#"<<str[i]<<"#"<<endl;
	}
	for(int i=0;i<w+2;i++)
	{
		cout<<"#";
	}
	cout<<endl;	
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll          long long int
#define pb          push_back
#define pll         pair<ll,ll>
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mod         998244353
#define mode        1000000007
#define inf         1000000000000000000LL
#define vl          vector<ll>
#define F           first
#define S           second
#define db          long double
#define sz(x)       (ll)x.size()
#define fix(n)      cout<<fixed<<setprecision(n)
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define all(x)      x.begin(),x.end()
#define mset(x)     memset(x,0,sizeof x)
#define pi          3.14159265358979323

const int N = 1e5+5;
ll n,c,k,t[N];

void solve()
{
       cin>>n>>c>>k;
       rep(i,1,n+1) cin>>t[i];
       sort(t+1,t+n+1);
       rep(i,1,n+1) t[i]+=k;
       ll cc=0;
       ll i=1;
       while(i<=n)
       {
              cc++;
              ll cnt=1;
              ll st=t[i];
              while(i<=n && cnt<=c && (t[i]-st<=k))  { i++; cnt++; }
       }
       cout<<cc;
}


int main()
{
    speed_up
    ll T=1;
    //cin>>T;
    while(T--)
        solve();
    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

int count = 0;

void quick_sort(int a[],int first,int last){

  int temp,k;
  int flag=1;
  int p=a[first];
  int i=first;
  int j=last;

  while(flag){
    while(a[i]<p)
      i++;
    
    while(p<a[j])
      j--;
    
    if(i<j){
      temp=a[i];
      a[i]=a[j];
      a[j]=temp;
      count++;
      i++;
      j--;
    }
    else
      flag=0;
  }

  if(first<i-1)
    quick_sort(a,first,i-1);
  
  if(j+1<last)
    quick_sort(a,j+1,last);
  
}


int main(void){
  int N, i;
  scanf("%d", &N);
  int p[N];
  for(i=0; i<N; i++)
    scanf("%d", &p[i]);

  quick_sort(p, 0, N-1);

  if(count == 1 || count == 0)
    printf("YES\n");
  else if(count > 1)
    printf("NO\n");


  return 0;
}


Measured memory_bytes: 128
import sys


def main():
    input = sys.stdin.readline

    r, c, k = map(int, input().split())

    items = [[0] * (c + 1) for _ in range(r + 1)]
    for _ in range(k):
        i, j, v = map(int, input().split())
        items[i][j] = v

    # dp[m][i][j] = (i行j列時点で、i行でm個のitemを取得している時の価値の最大値)
    dp = [[[0] * (c + 1) for _ in range(r + 1)] for _ in range(4)]

    for i in range(1, r + 1):
        for j in range(1, c + 1):
            for m in range(4):
                dp[m][i][j] = max(dp[3][i - 1][j], dp[m][i][j - 1])
            if items[i][j] > 0:
                for m in [2, 1, 0]:
                    dp[m + 1][i][j] = max(dp[m + 1][i][j],
                                          dp[m][i][j] + items[i][j])

    print(dp[3][r][c])


if __name__ == '__main__':
    main()


Measured memory_bytes: 421888
import re

N = int(input())
S = str(input())

ans = 0

inStr = [0,0,0,0,0,0,0,0,0,0]
for i in range(N - 2):
    inStr2 = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    if inStr[int(S[i])] == 0:
        inStr[int(S[i])] = 1
        for j in range(i + 1, N-1):
            inStr3 = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
            if inStr2[int(S[j])] == 0:
                inStr2[int(S[j])] = 1
                for k in range(j + 1, N):
                    if inStr3[int(S[k])] == 0:
                        inStr3[int(S[k])] = 1
                        ans = ans + 1
#                        print(S[i] + S[j] + S[k])

print(ans)



Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin>>s;
    rep(i,3) cout<<s[i];
}

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;


#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};


int main()
{
    int a,b;
    cin>>a>>b;
    int ans=-1;
    for (int i = b*10; i < (b+1)*10; i++)
    {
        if((int)(i*0.08)==a)
        {
            ans=i;
            break;
        }
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int dx[] = { -1, 0, 1, 0 }; const int dy[] = { 0, 1, 0, -1 };

struct UnionFind {
	vector<int> v;
	UnionFind(int n) : v(n)  { for (int i = 0; i < n; i++) v[i] = i; }
	int  find(int x)         { return v[x] == x ? x : v[x] = find(v[x]); }
	void unite(int x, int y) { v[find(x)] = find(y); }
};

ll gcd(ll a, ll b) {
	if (a < b)
		swap(a, b);
	while (a%b != 0) {
		a %= b;
		swap(a, b);
	}
	return b;
}

int main() {
	map<int, int> mpii;
	FOR(i, 1, 40000)
		mpii[i*i] = i;
	int p, q;
	cin >> p >> q;
	q /= gcd(p, q);
	set<int> soinsu;
	int copy = q;
	FOR(i,2,sqrt(copy)+1) {
		while (q%i == 0) {
			q /= i;
			soinsu.insert(i);
		}
	}
	soinsu.insert(q);
	ll ans = 1;
	for (int a : soinsu)
		ans *= a;
	cout <<ans << endl;
}

Measured memory_bytes: 4916
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <bitset>
using namespace std;

#define MOD 1000000007

int N, X, Y, Z;
int dp[41][1<<18];

int main() {
  cin >> N >> X >> Y >> Z;

  const int MASK = (1<<(X+Y+Z)) - 1;
  const int NG = (1<<(Z-1)) | (1<<(Y+Z-1)) | (1<<(X+Y+Z-1));

  for (int k=1; k<=10; k++) dp[0][(1<<(k-1)) & MASK] += 1;
  for (int i=1; i<N; i++) {
    for (int b=0; b<=MASK; b++) {
      if (dp[i-1][b] == 0) continue;
      for (int k=1; k<=10; k++) {
        int nb = ((b<<k) | (1<<(k-1))) & MASK;
        if ((nb & NG) == NG) continue;
        dp[i][nb] = (dp[i][nb] + dp[i-1][b]) % MOD;
      }
    }
  }
  int p = 1;
  for (int i=0; i<N; i++) {
    p = (10LL*p) % MOD;
  }
  int s = 0;
  for (int b=0; b<=MASK; b++) {
    s += dp[N-1][b];
    s %= MOD;
  }
  s = MOD - s;
  cout << (p + s) % MOD << "\n";
  return 0;
}


Measured memory_bytes: 39168
#include <assert.h>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <bitset>
typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const ll MOD7 = 1000000007;
ll x[100010] = {};
ll y[100010] = {};

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

  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> x[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> y[i];
  }

  ll xx = 0;
  for (int i = 1; i <= n; i++) {
    xx += (i - 1) * x[i] - (n - i) * x[i];
    xx %= MOD7;
  }
  ll yy = 0;
  for (int i = 1; i <= m; i++) {
    yy += (i - 1) * y[i] - (m - i) * y[i];
    yy %= MOD7;
  }

  cout << xx * yy % MOD7 << endl;
  return 0;
}


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

ll dp[44][1<<18];

int main(){
  int N,X,Y,Z; cin>>N>>X>>Y>>Z;
  ll ans=1;
  rep(i,N) (ans*=10)%=MOD;
  int ng=0;
  ng|=1<<Z;
  ng|=1<<(Y+Z);
  ng|=1<<(X+Y+Z);
  int mask=1<<(X+Y+Z+1); mask--;
  dp[0][1]=1;
  rep(i,N) rep(j,mask+1){
    for(int k=1;k<=10;k++){
      int tmp=((j<<k)&mask)+1;
      if((tmp&ng)==ng) continue;
      (dp[i+1][tmp]+=dp[i][j])%=MOD;
    }
  }
  rep(i,mask){
    (ans-=dp[N][i])%=MOD;
  }
  cout<<(ans+MOD)%MOD<<endl;
  return 0;
}


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

#define int long long
#define rep(i,a,n) for(int i = a; i < n; i++)
#define pb push_back
#define eb emplace_back
#define dump(x) cout << #x << " = " << (x) << endl
#define chk() cout << "now" << endl;
#define SORT(c) sort((c).begin(), (c).end())
#define SORTG(c) sort((c).begin(), (c).end(), greater<int>());
#define fi first
#define se second
  
typedef pair<int,int> P;
typedef vector<int> vi;

int N,K;
string S;
vector<P> ctn;

signed main() {
    cin>>N>>K;
    cin>>S;

    int n=0;
    if(S[0]=='0') ctn.pb(P(0,1));
    rep(i,0,N) {
        n++;
        if(i<N-1 and S[i]!=S[i+1]) {
            ctn.pb(P(n,S[i]-'0'));
            n=0;
        }
        if(i==N-1) ctn.pb(P(n,S[i]-'0'));
    }
    if(S[N-1]=='0') ctn.pb(P(0,1));

    int ret=0,flag=false;
    rep(i,0,2*K+1) {
        if(i==ctn.size()) {
            flag=true; 
            break;
        }
        ret+=ctn[i].fi;
    }
    int MAX=ret;
    if(flag==false) {
        rep(i,1,ctn.size()) {
            if(2*i+2*K>=ctn.size()) break;
            ret=ret+ctn[2*i+2*K-1].fi+ctn[2*i+2*K].fi-ctn[2*i-2].fi-ctn[2*i-1].fi;
            MAX=max(ret,MAX);
        }
    }
    cout<<MAX<<endl;
    return 0;
}




  




Measured memory_bytes: 2548
#include <iostream>
#include <string>
#include <vector>

int main(int argc, char* argv[])
{
  std::string s;
  std::string t;
  std::cin >> s;

  for (std::string::iterator it = s.begin(); it!= s.end(); it++) {
    if (*it == ',') {
      t.push_back(' ');
    } else {
      t.push_back(*it);
    }
  }

  std::cout << t << std::endl;
  return 0;
}


Measured memory_bytes: 256
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

a,b = input().split()
if len(a)>2:
    a1 = int(a[:-2:])
    a2 = int(a[-2::])
    b1 = int(float(b))
    b2 = int(b[2::])
    print(a1*b1*100+a1*b2+a2*b1+a2*b2//100)
else:
    a2 = int(a)
    b1 = int(float(b))
    b2 = int(b[2::])
    print(a2*b1+a2*b2//100)


Measured memory_bytes: 68880
dic = {((0, 0), (0, 1), (0, 2), (0, 3), (0, 4),
        (1, 0), (1, 4),
        (2, 0), (2, 1), (2, 2), (2, 3), (2, 4)):"0",

       ((0, 0), (0, 1), (0, 2), (0, 3), (0, 4)):"1",

       ((0, 0), (0, 2), (0, 3), (0, 4),
        (1, 0), (1, 2), (1, 4),
        (2, 0), (2, 1), (2, 2), (2, 4)):"2",

       ((0, 0), (0, 2), (0, 4),
        (1, 0), (1, 2), (1, 4),
        (2, 0), (2, 1), (2, 2), (2, 3), (2, 4)):"3",

       ((0, 0), (0, 1), (0, 2),
        (1, 2),
        (2, 0), (2, 1), (2, 2), (2, 3), (2, 4)):"4",

       ((0, 0), (0, 1), (0, 2), (0, 4),
        (1, 0), (1, 2), (1, 4),
        (2, 0), (2, 2), (2, 3), (2, 4)):"5",

       ((0, 0), (0, 1), (0, 2), (0, 3), (0, 4),
        (1, 0), (1, 2), (1, 4),
        (2, 0), (2, 2), (2, 3), (2, 4)):"6",

       ((0, 0), 
        (1, 0),
        (2, 0), (2, 1), (2, 2), (2, 3), (2, 4)):"7",

       ((0, 0), (0, 1), (0, 2), (0, 3), (0, 4),
        (1, 0), (1, 2), (1, 4),
        (2, 0), (2, 1), (2, 2), (2, 3), (2, 4)):"8",

       ((0, 0), (0, 1), (0, 2), (0, 4),
        (1, 0), (1, 2), (1, 4),
        (2, 0), (2, 1), (2, 2), (2, 3), (2, 4)):"9",

       ((0, 0),
        (1, -1), (1, 0), (1, 1),
        (2, 0)):"+",

       ((0, 0),
        (1, 0), 
        (2, 0)):"-",

       ((0, 0), ):"*"}


n = int(input())
mp = [[0] * 201 for _ in range(201)]
for _ in range(n):
  x1, y1, x2, y2 = map(int, input().split())
  if x1 == x2:
    y1, y2 = min(y1, y2), max(y1, y2)
    for y in range(y1, y2 + 1):
      mp[y][x1] = 1

  elif y1 == y2:
    x1, x2 = min(x1, x2), max(x1, x2)
    for x in range(x1, x2 + 1):
      mp[y1][x] = 1

checked = [[False] * 201 for _ in range(201)]
vec = ((1, 0), (0, -1), (-1, 0), (0, 1))


def search(x, y, ix, iy, stack):
  for dx, dy in vec:
    if not 0 <= y + dy < 201 or not 0 <= x + dx < 201:continue
    if mp[y + dy][x + dx] == 1 and not checked[y + dy][x + dx]:
      checked[y + dy][x + dx] = True
      stack.append((x + dx - ix, y + dy - iy))
      search(x + dx, y + dy, ix, iy, stack)

s = ""
for x in range(201):
  for y in range(201):
    if mp[y][x] == 1 and not checked[y][x]:
      checked[y][x] = True
      stack = [(0, 0)]
      search(x, y, x, y, stack)
      stack.sort()
      s += dic[tuple(stack)]

print(eval(s))


Measured memory_bytes: 6288
def main():
    L, R = map(int, input().split())
    # 60 の相異なる素因数は 3, 673 の 2つ
    if L + 672 <= R:
        print(0)
        return
    s = set()
    for i in range(L, R + 1):
        for j in range(i + 1, R + 1):
            if i * j % 2019 == 0:
                print(0)
                return
            s.add(i * j % 2019)
    print(min(s))
    return


main()


Measured memory_bytes: 3188
import java.util.*;
 
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int X = sc.nextInt();
        int nam = 0;
        int cont = 0;
      
      for(int i=0;i<N;i++){
        nam += sc.nextInt();
        if(nam<=X){cont++;}
      }

      System.out.print(cont+1);

      
      
      
      
      


      
    }
}

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

typedef long long int ll;
ll powk(ll a, ll n = 2){
    ll r = 1;
    for(ll i = 0;i < n;i++){
        r *= a;
    }

    return r;
}

int main()
{
    ll n;
    cin >> n;
    vector<ll> a(n);
    for(ll i = 0;i < n;i++){
        cin >> a[i];
    }

    ll ans = 1000000000;
    for(ll i = -100;i <= 100;i++){
        ll t = 0;
        for(ll j = 0;j < n;j++){
            t += (a[j] - i) * (a[j] - i);
        }
        ans = min(ans, t);
    }

    cout << ans;

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{

	public static void main (String[] args) {

		Scanner scan = new Scanner(System.in);

		int N = scan.nextInt();
		int Y = scan.nextInt();

		int counta =0;
		int countb =0;
		int countc =0;


		counta = Y /10000;
		countb = (Y - 10000 * counta)/5000;
		countc = ( (Y - 10000 * counta)-(5000*countb) )/1000;



		int countsum = counta + countb + countc;

		//List<Integer> list = new ArrayList<>();
		//List<String> pattern = new ArrayList<>();



		loop: for(int i=counta ; i>=0; i--) {

			int cflag = countc;

			for(int j=countb; j>=0; j-- ) {


				countsum= i+j+cflag;

				//list.add(countsum);

				if(countsum==N) {

				String pat = i + " " + j + " " + cflag;

				System.out.println(pat);

				break loop;

				}

				//pattern.add(pat);

				cflag = cflag + 5;


				if(i==0 && j==0)
				{System.out.println("-1 -1 -1");
				}

			}

			countb = countb + 2;


		}


		/*
		for(int i=0; i<list.size() ;i++) {

			int counter = list.get(i);
			//System.out.println(counter);

			if (counter==N) {

				String ans = pattern.get(i);
				System.out.println(ans);
				break;

			}
			else if(i == list.size()-1) {

				System.out.println("-1 -1 -1");

			}
		}
		*/



	}

}

Measured memory_bytes: 21716
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <numeric>
#include <functional>
#include <sstream>
#include <iostream>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cassert>
using namespace std;

#define EPS 1e-12
#define ull unsigned long long
#define ll long long
#define VI vector<ll>
#define PII pair<ll, ll> 
#define VVI vector<vector<ll> >
#define VVVI vector<vector<vector<ll>>>
#define VVVVI vector<vector<vector<vector<ll>>>>
#define REP(i,n) for(ll i=0,_n=(n);(i)<(ll)_n;++i)
#define REPR(i,n) for(ll i=(ll)(n)-1;0<=(i);--i)
#define RANGE(i,a,b) for(ll i=(ll)a,_b=(ll)(b);(i)<_b;++i)
#define RANGER(i,a,b) for(ll i=(ll)(b)-1,_a=(ll)(a);(_a)<=i;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define ALLR(c) (c).rbegin(), (c).rend()
#define PB push_back
#define MP(a, b) make_pair(a, b)
#define POPCOUNT __builtin_popcount
#define POPCOUNTLL __builtin_popcountll
#define CLEAR(table, v) memset(table, v, sizeof(table));
#define UNIFORM_DOUBLE(a, b) (((b-a)*(double)rand()/RAND_MAX)+a) // [a, b) 
#define UNIFORM_LL(a, b) (ll)UNIFORM_DOUBLE(a, b) // [a, b) 
#define IN(v, lo, hi) ((lo)<=(v) && (v)<(hi))
#define DD(v) cout<<#v<<": "<<v<<endl
#define FI first
#define SE second
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const map<T0, T1>& v) { for( typename map<T0, T1>::const_iterator p = v.begin(); p!=v.end(); p++ ){os << p->first << ": " << p->second << " ";} return os; }
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const pair<T0, T1>& v) { os << v.first << ": " << v.second << " "; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << " "; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const set<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const deque<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<vector<T> >& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << endl; } return os; }
template<typename T>void maxUpdate(T& a, T b) {a = max(a, b);}
template<typename T>void minUpdate(T& a, T b) {a = min(a, b);}
string YN(bool v) { return v ? "Yes":"No"; }
void uniq(VI& es) { sort(ALL(es)); es.erase(unique(ALL(es)), es.end()); }

#define INF (1LL<<60)
/*
i<j
j-i==Ai+Aj
j-Aj==Ai+i
*/
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N,M,W,H,K;
	while(cin>>N) {
		VI A(N);
		REP(i, N) cin>>A[i];
		map<ll, ll> h;
		REP(i, N) h[i-A[i]]++;
		ll ans=0;
		REP(i, N) {
			ans+=h[i+A[i]];
		}
		cout<<ans<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 27016
local function gcd(a,b)
    if b == 0 then
        return a
    else
        return gcd(b, a % b)
    end
end

local function gcdmany(tbl)
    local ans = tbl[1]
    for i=2,#tbl do
        ans = gcd(ans, tbl[i])
    end
    return ans
end

----

local N = io.read("n")
local A = {} for i=1,N do A[i] = io.read("n") end

local L, R = {}, {}
L[1] = A[1]
for i=2, N do
    L[i] = gcd(L[i-1], A[i])
end
R[N] = A[N]
for i=N-1, 1,-1 do
    R[i] = gcd(R[i+1], A[i])
end

local maxval = 0
maxval = math.max(maxval, R[2])
for i=2, N-1 do
    local g = gcd(L[i-1], R[i+1])
    maxval = math.max(maxval, g)
end
maxval = math.max(maxval, L[N-1])

print(maxval)

Measured memory_bytes: 8556
#include<iostream>
#include<algorithm>
#include<functional>
#include <string>
#include<iomanip>
#include<cstdio>
#include<math.h>
#include<stack>
#include<queue>
#include<cstring>
#include<vector>
typedef long long int ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EREP(i,n) for(int i=(n-1);i>=0;--i)
#define D(n,retu) REP(i,n){cin>>retu[i];}
#define mod 1000000007
#define MIN -93193111451418101
#define INF 931114518101
using namespace std;
typedef pair<ll, ll>P;
template<typename T>
void fill_all(T& arr, const T& v) {
	arr = v;
}
template<typename T, typename ARR>
void fill_all(ARR& arr, const T& v) {
	for (auto& i : arr) { fill_all(i, v); }
}
#define MAX_NUM 50
long long comb[MAX_NUM + 1][MAX_NUM + 1];

static void calc_comb()
{
	for (uint32_t i = 0; i <= MAX_NUM; i++) {
		for (uint32_t j = 0; j <= i; j++) {
			if ((j == 0) || (i == j)) {
				comb[i][j] = 1;
			}
			else {
				comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
			}
		}
	}
}
#define yo 100001
//------------------変数-----------------------//
ll n;
//-------------------関数----------------------//
ll par[100000], depth[100000];
ll f[305][305];
bool flag[301][301] = {};
ll cnt = 0;
bool floyd()
{
	for (int k = 0; k < n; ++k)
	{
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (flag[i][j] &&f[i][k] + f[k][j] < f[i][j]) { return false; }
				if (f[i][k] + f[k][j] == f[i][j]) { 
					if (flag[i][j]) { 
						cnt -= f[i][j];  
					} flag[j][i] = false; flag[i][j] = false;
				}
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
				f[j][i] = f[i][j];
			}
		}
	}
	return true;
}

int main() {
	fill_all(f, (ll)INF);
	cin >> n;
	REP(i, n) {
		REP(j,n){
			ll a, b, c; cin >> a;
			if (a) {
				f[i][j] = a; 
				cnt += a;
				flag[i][j] = true;
			}
		}
	}
	cnt /= 2;
	if (!floyd()) { cout << -1 << endl; return 0; }
	cout << cnt << endl;

}


Measured memory_bytes: 1024
n,m = gets.split.map(&:to_i)
x = gets.split.map(&:to_i).sort
y = Array.new(m-1)
if m <= n
    puts 0
    exit
end
for i in 0..m-2
    y[i] = x[i+1]-x[i]
end
y.sort!
ans = y[0..m-n-1].inject(:+)
puts ans

Measured memory_bytes: 10480
#include<bits/stdc++.h>
#define rep(i,a,n) for (int i = a; i < n; i++)
#define per(i,n,a) for (int i = n - 1; i >= a; i--)
using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    int c = stoi(a + b);
    rep(i, 1, 1000) {
        if (i * i == c) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>

long long int max(long long int a, long long int b){
  if(a>b) return a;
  else return b;
}

int main(void){
  int i, N, count;
  long long int sum, A[200001];
  char S[4], prev;

  scanf("%d", &N);
//  printf("%d\n", N);
  for(i=0; i<N; i++){
    scanf("%lld", &A[i]);
//    printf("%d\n", A[i]);
  }
  sum=0;
  for(i=1; i<N; i++){
    sum+=max(0, A[i-1]-A[i]);
    A[i]=max(A[i-1], A[i]);
 //   printf("%d %d\n", sum, A[i]);
  }
  printf("%lld", sum);
  return 0;
}

Measured memory_bytes: 3260
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define pb push_back

#define speed ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

template<class L,class R> ostream& operator<<(ostream& cout,pair<L, R> P)
{return cout<<'('<<P.x<<','<< P.y<<')';}
template<class T> ostream& operator<<(ostream& cout,vector<T> V)
{cout<<"[ ";for(auto v:V)cout<<v<<' ';return cout<<']';}


int n;
vector<pair<int,int>> inp;
bool cmp(pair<int,int> p1, pair<int,int> p2)
{
	return (make_pair(p1.y,p2.x)<make_pair(p2.y,p1.x));
}
vector<int> eps;
vector<bool> done;
vector<int> dp;
int f(int ix)
{
	if(ix<0){return 0;}
	if(done[ix]){return dp[ix];}
	done[ix]=1;
	dp[ix]=f(ix-1);
	int fix=(upper_bound(eps.begin(),eps.end(),inp[ix].x)-eps.begin());
	dp[ix]=max(dp[ix],1+f(fix-1));
	return dp[ix];
}
signed main()
{
	speed
	cin>>n;
	for (int i = 0; i < n; ++i)
	{
		int x,l;cin>>x>>l;
		inp.push_back({x-l,x+l});
	}
	done.assign(n,0);dp.assign(n,0);
	sort(inp.begin(),inp.end(),cmp);

	for(auto it:inp){eps.push_back(it.y);}
	dp[0]=1;done[0]=1;
	cout<<f(n-1);
}

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

#ifdef DEBUG
#define PRINT(x)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#x<<" = "<<(x)<<endl;
#define PRINTA(a,first,last)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#a<<"["<<(first)<<", "<<(last)<<")"<<endl;\
    for (int _i=(first);_i<(last);++_i){cout<<#a<<"["<<_i<<"] = "<<(a)[_i]<<endl;}
#define PRINTI(a,i)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#a<<"["<<#i<<"] = "<<#a<<"["<<(i)<<"] = "<<(a)[i]<<endl;
#else
#define PRINT(x)
#define PRINTA(a,first,last)
#define PRINTI(a,i)
#endif

#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);--i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define MOD 1000000007
//#define MOD 998244353

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

template <class T, class U> void amax(T& x, U y) {if (x < y) x = y;}
template <class T, class U> void amin(T& x, U y) {if (x > y) x = y;}

template <class T, class U>
std::ostream& operator<<(std::ostream &os, const std::pair<T, U> &p) {
	os << "(" << p.first << ", " << p.second << ")";
	return os;
}
 
template <class T>
std::ostream& operator<<(std::ostream &os, const std::vector<T> &v) {
    os << "[";
	for (int i = 0; i < v.size(); ++i) {
        if (i) {
            if (i % 5 == 0) {
                os << ",\n ";
            } else {
                os << ", ";
            }
        }
		os << v[i];
	}
	os << "]";
	return os;
}

template <class T>
using vec2 = vector<vector<T>>;

template <class T>
using vec3 = vector<vector<vector<T>>>;

const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int X;
    cin >> X;
    cout << (X >= 30 ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 3684
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
int main() {
  int k, a, b;
  cin >> k >> a >> b;
  for(int i = a; i <= b; i++) {
    if(i % k == 0) {
      cout << "OK";
      return 0;
    }
  }
  cout << "NG";
}


Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};


int main(){
    int x;
    cin >> x;
    int ans = 0;
    while (ans*(ans+1)/2<x) ans++;
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3668
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

ans = b[a[0]-1]

for i in range(1,n):
    ans += b[a[i]-1]
    if a[i] == a[i-1] +1:
        ans += c[a[i-1]-1]

print(ans)

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

using namespace std;

int main() {
	int a, b, c, d;
	int t = 0;
	scanf("%d %d %d %d", &a, &b, &c, &d);
	while (a > 0 && c > 0) {
		if (t == 0) {
			c -= b;
			t = 1;
		} else {
			a -= d;
			t = 0;
		}
	}
	if (a > 0) printf("Yes\n");
	else printf("No\n");
	return 0;
}


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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (a); i < (b); i++)
#define revrepeat(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define CYES cout << "Yes" << endl
#define CNO cout << "No" << endl
#define SPC(x) cout << fixed << setprecision(x)
#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a, 0xff, sizeof(a))

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<vector<ll>> vll;
typedef pair<int, int> P;
typedef complex<ld> Point;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MAX_V = 1e5 + 5;
const int MAX_N = 1e5 + 5;
const double PI = acos(-1);

ll dp[1000000][2]; // digit, look_forward_flag(0: exact, 1: look_forward)

int main() {
    string s;
    cin >> s;
    int n = s.size();
    reverse(all(s));
    dp[0][0] = 0;
    dp[0][1] = INF;
    rep(i, n) {
        int c = s[i] - '0';
        if (i == n - 1) {
            dp[i + 1][0] = min(dp[i][0] + c, dp[i][1] + c + 1);
            dp[i + 1][1] = min(dp[i][0] + (11 - c), dp[i][1] + (10 - c));
        } else {
            dp[i + 1][0] = min(dp[i][0] + c, dp[i][1] + c + 1);
            dp[i + 1][1] = min(dp[i][0] + (10 - c), dp[i][1] + (10 - (c + 1)));
        }
        // debug(i);
        // debug(dp[i + 1][0]);
        // debug(dp[i + 1][1]);
    }
    out(min(dp[n][0], dp[n][1]));
    return 0;
}


Measured memory_bytes: 17028
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=10100100100100100;
int main(){
    int n;cin >> n;
    vector<ll> a(3*n);
    for(int i=0;i<3*n;i++) cin >> a[i];
    ll ans=0;
    sort(a.rbegin(),a.rend());
    for(int i=1;i<2*n;i+=2) ans+=a[i];
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double lld;
ll MOD = (1e9)+7;
const int dr[] = {+1, -1, +0, +0, +1, -1, +1, -1};
const int dc[] = {+0, +0, +1, -1, +1, -1, -1, +1};
const int kx[] = {+1, +2, -1, -2, +1, +2, -1, -2};
const int ky[] = {+2, +1, +2, +1, -2, -1, -2, -1};
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
inline void fastIO(){
  ios_base::sync_with_stdio(0);cin.tie(0);
}
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }

#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif

int n,m,size_subtree=0,ans=0;
vector<vector<int>>adj(202020);
vector<bool>vis(202020,false);
void DFS(int source){
  vis[source]=true;
  for(auto node:adj[source]){
    if(!vis[node]){
      size_subtree++;
      DFS(node);
    }
  }
}
int main(){
  fastIO();
  cin>>n>>m;
  for(int i=0;i<m;i++){
    int nodeA,nodeB;
    cin>>nodeA>>nodeB;
    adj[nodeA].push_back(nodeB);
    adj[nodeB].push_back(nodeA);
  }
  for(int i=1;i<=n;i++){
    if(!vis[i]){
      size_subtree=0;
      DFS(i);
      ans=max(ans,size_subtree);
    }
  }
  cout<<ans+1<<endl;
  return 0;
}

Measured memory_bytes: 20312
N,K = map(int,input().split())
A = list(map(int,input().split()))
MOD = 10**9+7

if all(a>=0 for a in A):
    A.sort()
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if all(a<0 for a in A):
    A.sort(reverse=K%2==0)
    ans = 1
    for _ in range(K):
        ans *= A.pop()
        ans %= MOD
    print(ans)
    exit()
if N==K:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans)
    exit()

arr = []
for a in A:
    if a < 0:
        arr.append((-a,1))
    else:
        arr.append((a,0))

arr.sort()
pz = []
ng = []
ans = 1
for _ in range(K):
    v,s = arr.pop()
    if s:
        ng.append(v)
    else:
        pz.append(v)

for v in ng:
    ans *= v
    ans %= MOD
for v in pz:
    ans *= v
    ans %= MOD
if len(ng)%2 == 0:
    print(ans)
    exit()

b = pz[-1] if pz else None
c = ng[-1] if ng else None
a = d = None
while arr and (a is None or d is None):
    v,s = arr.pop()
    if s:
        if a is None:
            a = v
    else:
        if d is None:
            d = v

if (a is None or b is None) and (c is None or d is None):
    assert False

if a is None or b is None:
    ans *= d * pow(c,-1,MOD)
elif c is None or d is None:
    ans *= a * pow(b,-1,MOD)
else:
    if a*c > b*d:
        ans *= a * pow(b,-1,MOD)
    else:
        ans *= d * pow(c,-1,MOD)
ans %= MOD
print(ans)

Measured memory_bytes: 39680
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using vi=vector<int>;
using P = pair<int,int>;
using Graph = vector<vector<int>>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    int maxi=a[0];
    ll ans=0;
    rep(i,n){
        if(a[i]<maxi){
            ans+=(maxi-a[i]);
        }else{
            maxi=a[i];
        }
    } 
    cout << ans << "\n";
    return 0;
}   

Measured memory_bytes: 3988