akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using ll = long long;
#define rep(i ,n) for(ll i = 1 ; i <= (n) ; i ++ )
#define all(x) (x).begin(),(x).end()

using namespace std;
using Graph = vector<vector<int>>;


int main() {
  ll x;
  cin>>x;
  ll a,b;
  ll y=sqrt(x);
 // cout <<y<<endl;
  rep(i,y){
    if(x%i==0){
     
      for(ll j = 0 ; j <=pow(x,0.7)  ; j ++ ){
      //  cout<<pow(x,0.2)<<endl;
        if(j*j*j*j+j*j*j*(j-i)+j*j*(j-i)*(j-i)+j*(j-i)*(j-i)*(j-i)+(j-i)*(j-i)*(j-i)*(j-i)==x/i){
          a=j;
          b=j-i;
          break;
        }
      }
       if(!(a==0&&b==0)) break; 
    }
  }
  
  cout<<a<<" "<<b<<endl;
}

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


int main() {
  int r,g,b;cin >> r >> g >> b;
  if ((10*g+b)%4 == 0){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }

}       

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;

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

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 7;
constexpr long long LINF = 1e18;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;

void solve() {
    int N, K, L;
    cin >> N >> K >> L;
    Graph T(N), C(N);
    for (int i=0; i<K; ++i) {
        int a, b;
        cin >> a >> b;
        T[a-1].push_back(b-1);
        T[b-1].push_back(a-1);
    }
    for (int i=0; i<L; ++i) {
        int a, b;
        cin >> a >> b;
        C[a-1].push_back(b-1);
        C[b-1].push_back(a-1);
    }

    vector<pair<int, int>> color(N, {-1, -1});
    queue<int> que;
    for (int i=0; i<N; ++i) {
        if (color[i].first == -1) {
            color[i].first = i;
            que.push(i);
            while (!que.empty()) {
                int cur = que.front(); que.pop();
                for (int nx : T[cur]) {
                    if (color[nx].first == -1) {
                        color[nx].first = i;
                        que.push(nx);
                    }
                }
            }
        }
        if (color[i].second == -1) {
            color[i].second = i;
            que.push(i);
            while (!que.empty()) {
                int cur = que.front(); que.pop();
                for (int nx : C[cur]) {
                    if (color[nx].second == -1) {
                        color[nx].second = i;
                        que.push(nx);
                    }
                }
            }
        }
    }

    map<pair<int, int>, int> mp;
    for (auto p : color) ++mp[p];
    for (int i=0; i<N; ++i) {
        cout << mp[color[i]];
        if (i == N-1) cout << '\n';
        else cout << ' ';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}


Measured memory_bytes: 27776
#include<bits/stdc++.h>
#define ll long long
#define in insert
#define pb push_back
#define endl '\n'
#define ub upper_bound
#define lb lower_bound
#define pf pop_front
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);srand(time(0));
using namespace std;
ll mod=1e9+7;
void fun()
{
	ll n;cin>>n;
	ll r=n*n;
	ll p=r*n;
	cout<<n+r+p;
}
int main()
{
    fast;
    int t=1;
    //cin>>t;
    while(t--)
    {
    	fun();
	}
}

Measured memory_bytes: 3652
n = int(input())
a = list(map(int, input().split()))

z = 0
for i in range(n):
    z += a[i]
e = z % 2

y = (z ** 2) % 2000000014

x = 0
for j in range(n):
    x += a[j] ** 2
    x = x % 2000000014

w = int(((y - x) / 2) % 1000000007)
print(w)

Measured memory_bytes: 31448
a = []
for i in range(5):
    a.append(int(input() )) 


t =0
s = 0
for m in a:
    t += int(m/10) * 10
    if m%10 != 0:
        t = t + 10
    if 10 - (m%10) > s and m%10 !=0:
        s = 10 - (m%10)

print(t - s)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
//author:Um_nik
//date:2018/11/17
//title:Rearranging AGC 010 E

inline int gcd(int x,int y)
{
	return (y==0?x:gcd(y,x%y));
}

typedef long long ll;
typedef pair<int,int> pii;

const int N=2020;
const int V=40020;

int n,m;
int a[N];
bool b[N][N];
int ans[N];
bool inAns[N];
int ansSz=0;
int lastNotCoprime[N];
int minOnSuff[N];
int comp[V];
vector<int> g[V];

int C;
int bestForCol[N];

map<int,int> primeId;
int getId(int y)
{
	if(primeId.count(y)>0) return primeId[y];
	primeId[y]=m;
	return m++;
}

void dfs(int v)
{
	comp[v]=C;
	for(int u:g[v]){
		if(u<n&&inAns[u]) continue;
		if(comp[u]!=-1) continue;
		dfs(u);
	}
	return;
}

void color()
{
	for(int i=0;i<m;i++)
		comp[i]=-1;
	C=0;
	for(int i=0;i<n;i++)
	{
		if(inAns[i]) continue;
		if(comp[i]!=-1) continue;
		dfs(i);
		C++;
	}
	return;
}

int main()
{
	scanf("%d",&n);
	m=n;
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		int x=a[i];
		for(int y=2;y*y<=x;y++){
			if(x%y!=0) continue;
			int id=getId(y);
			g[id].push_back(i);
			g[i].push_back(id);
			while(x%y==0) x/=y;
		}
		if(x!=1)
		{
			int id=getId(x);
			g[id].push_back(i);
			g[i].push_back(id);
		}
	}
	
	for(int i=0;i<n;i++) 
		for(int j=i+1;j<n;j++) 
			if(gcd(a[i],a[j])>1) 
				b[i][j]=b[j][i]=true;
	
	for(int i=0;i<n;i++) 
		minOnSuff[i]=1e9+2;
	for(int i=0;i<n;i++) 
		lastNotCoprime[i]=-1;
	while(ansSz!=n)
	{
		color();
		for(int i=0;i<C;i++)
			bestForCol[i]=-1;
		for(int i=0;i<n;i++)
		{
			if(inAns[i]) continue;
			if(minOnSuff[lastNotCoprime[i]+1]<a[i]) continue;
			if(bestForCol[comp[i]]==-1||a[bestForCol[comp[i]]]>a[i])
				bestForCol[comp[i]]=i;
		}
		
		int id=-1;
		for(int i=0;i<C;i++)
		{
			if(bestForCol[i]==-1) continue;
			if(id==-1||a[bestForCol[i]]>a[id])
				id=bestForCol[i];
		}
		if(id==-1) throw;
		inAns[id]=true;
		ans[ansSz++]=a[id];
		for(int i=0;i<ansSz;i++)
			minOnSuff[i]=min(minOnSuff[i],a[id]);
		
		for(int i=0;i<n;i++) if(b[id][i])	lastNotCoprime[i]=ansSz-1;
	}
	for(int i=0;i<ansSz;i++)
		printf("%d ",ans[i]);
	printf("\n");
	
	return 0;
}

Measured memory_bytes: 5504
//
// Created by 李青坪 on 2018/10/26.
//

#include <cstdio>

using namespace std;
#define MAXN 500001
int heaps[MAXN];
int n;

void exchange(int i, int j){
    int temp = heaps[i];
    heaps[i] = heaps[j];
    heaps[j] = temp;
}

int maxHeapJudge(int i){
    int l = i*2;
    int r = l+1;
    int largest = i;
    if (l <= n && heaps[l] > heaps[i]){
        largest = l;
    }
    if (r <= n && heaps[r] > heaps[largest]){
        largest = r;
    }
    if (largest != i){
        exchange(i, largest);
        maxHeapJudge(largest);
    }
}

int makeHeap(){
    for (int i = n/2; i >=1; --i) {
        maxHeapJudge(i);
    }
}

void print(){
    for (int i = 1; i <= n; ++i) {
        printf(" %d", heaps[i]);
    }
    printf("\n");
}

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &heaps[i]);
    }
    makeHeap();
    print();
}
/*
10
4 1 3 2 16 9 10 14 8 7

 */


Measured memory_bytes: 4564
import java.util.Scanner;

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

        final int N = sc.nextInt();
        final int K = sc.nextInt();
        System.out.println(Integer.toString(Integer.parseInt(Integer.toBinaryString(N), 2), K).length());
    }
}


Measured memory_bytes: 21332
import sys


stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

li = [1, 2, 3]
a = ni()
b = ni()
li.remove(a)
li.remove(b)
print(li[0])

Measured memory_bytes: 3060
#include <iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
char a,b;  
int main(){
cin>>a>>b;
if(a<b){
    cout<<"<"<<endl;
}
else if(b<a){
    cout<<">"<<endl;
}
else{
    cout<<"="<<endl;
}
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
using namespace std;
//cout <<  << endl;
typedef long long int ll;
typedef long double ld;

using Graph = vector<vector<ll>>;

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; }

#define MAX_N 2010

const long long INF = 1LL << 60;

//境界値に注意！！！
int main() {
    ll x,y,z,ans=0;
    cin >> x >> y >> z;
    ll s=y+z;
    while(ans*s<=x-z){
        ans++;
    }
    cout << ans-1 << endl;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	N := nextInt()
	A := make([]int, N+1)
	boxes := make([]int, N+1)
	counts := make([]int, N+1)

	for i := 1; i <= N; i++ {
		A[i] = nextInt()
	}
	for i := N; i >= 1; i-- {
		a := A[i]

		if a == counts[i]%2 {
			continue
		}
		boxes[i] = 1

		for j := 1; j*j <= i; j++ {
			if i%j == 0 { // 割り切れたら数を追加する
				counts[j]++
				k := i / j

				if j != k {
					counts[k]++
				}
			}
		}
	}

	fmt.Println(counts[1])
	first := true
	for i := 1; i <= N; i++ {
		if boxes[i] == 1 {
			if first {
				fmt.Printf("%d", i)
				first = false
			} else {
				fmt.Printf(" %d", i)
			}
		}
	}
	fmt.Println()

	// debug
	// for i := 1; i <= N; i++ {
	// 	fmt.Printf("%d ", counts[i])
	// }
	// fmt.Println()
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024 // 1 MB
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func nextString() string {
	stdin.Scan()
	return stdin.Text()
}

func nextBytes() []byte {
	stdin.Scan()
	return stdin.Bytes()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextString())
	return i
}

func nextInt64() int64 {
	i, _ := strconv.ParseInt(nextString(), 10, 64)

	return i
}


Measured memory_bytes: 7424
#include <cstdio>
#include <cstring>
using namespace std;
char s1[20],s2[20],s3[20];
int main() {
	scanf("%s %s %s",s1,s2,s3);
	if (s1[strlen(s1)-1]==s2[0]&&s2[strlen(s2)-1]==s3[0])
		printf("YES\n");
	else printf("NO\n");
	return 0;
}

Measured memory_bytes: 128
//
//  main.cpp
//  앳코
//
//  Created by 김도훈 on 2020/09/13.
//  Copyright © 2020 김도훈. All rights reserved.
//

#include <iostream>
using namespace std;

int main() {
    int x;
    cin >> x;
    if (x) cout << 0;
    else cout << 1;
    return 0;
}


Measured memory_bytes: 3628
using namespace std;
int main(){
	int n,s;
	while(cin>>n,n){
		s=1;
		for(int i=2;i*i<=n;i++){
			if(n%i)continue;
			if(i*i<n)s+=n/i+i;
			else s+=i;
		}
		if(n==1)s=0;
		cout<<(s<=n?s<n?"deficient":"perfect":"abundant")<<" number"<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
n=int(input())
li=[list(map(int,input().split())) for i in range(n)]
ans=[[0,0,0] for i in range(n)]
ans[0]=li[0]
for i in range(n-1):
    ans[i+1][0]=max(ans[i][1],ans[i][2])+li[i+1][0]
    ans[i+1][1]=max(ans[i][0],ans[i][2])+li[i+1][1]
    ans[i+1][2]=max(ans[i][1],ans[i][0])+li[i+1][2]
print(max(ans[n-1]))
    


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

int main(){
  int A,B;
  string S;
  cin>>A>>B;
  cin>>S;
  if(!(S.at(A)=='-')){
    cout<<"No"<<endl;
    return 0;
  }
  S.erase(S.begin()+A);
  if(!(S.length()==A+B)){
    cout<<"No"<<endl;
    return 0;
  }
  for (int i=0;i<A+B;i++){
    if(!(isdigit(S.at(i)))){
      cout<<"No"<<endl;
      return 0;
    }
  }
   cout<<"Yes"<<endl;
    return 0;
}



  

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF INT_MAX/3

#define MAX_N 1000

//// UnionFind
struct UnionFind{
	vector<int> v;
	UnionFind(int n) : v(n, -1) {}

	int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }
	bool unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y) return false;
		if (-v[x] < -v[y]) swap(x, y);
		v[x] += v[y]; v[y] = x;
		return true;
	}
	bool root(int x) { return v[x] < 0; }
	bool same(int x, int y) { return find(x) == find(y); }
	int size(int x) { return -v[find(x)]; }
};

int n;
int k,l;
P ps[500005];

int main(){
	cin.sync_with_stdio(false);
	cin>>n>>k>>l;
	UnionFind uf(n);
	rep(i,k){
		int a,b;
		cin>>a>>b;
		a--;b--;
		uf.unite(a,b);
	}
	UnionFind uff(n);
	rep(i,l){
		int a,b;
		cin>>a>>b;
		a--;b--;
		uff.unite(a,b);
	}
	rep(i,n){
		ps[i]=P(uf.find(i),uff.find(i));
	}
	sort(ps,ps+n);
	rep(i,n){
		P pp=P(uf.find(i),uff.find(i));
		int size=upper_bound(ps,ps+n,pp)-lower_bound(ps,ps+n,pp);
		printf("%d%c", size,i==n-1?'\n':' ');
	}
	return 0;
}


Measured memory_bytes: 3840
use std::io;

fn read_line()-> String {
    let mut s = String::new();
    let _ = io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn harshad(mut c:i32,mut mods:i32) -> i32 {
	if c / 10 == 0 {
		mods = mods + (c%10);
		mods
	}else{
		mods = mods + (c % 10);
		c = c / 10;
		harshad(c,mods)
	}

}


fn main() {
	let N = read_line().parse::<i32>().unwrap();
	let h = harshad(N,0);

	if N % h == 0 {
		println!("Yes");
	}else{
		println!("No");
	}

}


Measured memory_bytes: 4352
#include <stdio.h>
#include <string.h>

int n;
char expressions[100][200];
int expressions_len[100];
int expression_number[100];
char input[500];
int input_len;

int memo_number[200];

int tansaku_number(int pos) {
	int i;
	int max=-0x10000000;
	int now;
	if(pos>=input_len)return 0;
	if(memo_number[pos]>0)return memo_number[pos]-1;
	for(i=0;i<n;i++) {
		if(strncmp(&input[pos],expressions[i],expressions_len[i])==0) {
			now=tansaku_number(pos+expressions_len[i]);
			now+=expression_number[i];
			if(now>max)max=now;
		}
	}
	memo_number[pos]=max+1;
	return max;
}

int memo_expression[2100];

int tansaku_expression(int rest) {
	int i;
	int result=0x10000000;
	int now;
	if(rest<0)return result;
	if(rest==0)return 0;
	if(memo_expression[rest]>0)return memo_expression[rest]-1;
	for(i=0;i<n;i++) {
		now=tansaku_expression(rest-expression_number[i]);
		now+=expressions_len[i];
		if(now<result)result=now;
	}
	memo_expression[rest]=result+1;
	return result;
}

int main(void) {
	int dataset_count;
	int i;
	int number;
	for(dataset_count=1;;dataset_count++) {
		scanf("%d",&n);
		if(n==0)break;
		for(i=0;i<n;i++) {
			scanf("%s%d",expressions[i],&expression_number[i]);
			expressions_len[i]=strlen(expressions[i]);
		}
		scanf("%s",input);
		input_len=strlen(input);
		memset(memo_number,0,sizeof(memo_number));
		memset(memo_expression,0,sizeof(memo_expression));
		number=tansaku_number(0);
		printf("Case %d: %d\n",dataset_count,tansaku_expression(number));
	}
	return 0;
}

Measured memory_bytes: 0
S = input()
output = 'Yes'
for i in range(len(S)):
    if (i + 1) % 2 == 1:
        if S[i] == 'L':
            output = 'No'
            break
    else:
        if S[i] == 'R':
            output = 'No'
            break

print(output)


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

using namespace std;

int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
#define rep(i,n) for(int i = 0;i<n;i++)

int main(){

    int N, K;
    cin >> N >> K;
    vector<int> ar(N);

    rep(i,N)cin >> ar[i];

    sort(ar.begin(),ar.end());
    int sum= 0;
    rep(i,K)sum+=ar[i];
    cout << sum << endl;


}



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

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    int bucket[N] = {0};

    for(int i = 0; i < M; ++i){
        int a, b;
        cin >> a >> b;
        bucket[a - 1] += 1;
        bucket[b - 1] += 1;
    }
    for(int i = 0; i < N; ++i) cout << bucket[i] << endl;
}

Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
fn main() {
    input!{
        n: usize,
        p: [usize; n],
    }
    let mut m = p[0];
    let mut ans = 1;
    for i in 1..n {
        if p[i] < m {
            ans += 1;
            m = p[i];
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 8444
import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
s=[[]for i in range(n+1)]
c=[0]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)
def dfs(v,t):
    c[v]=t
    for i in s[v]:
        if c[i]==t:
            return False
        if c[i]==0 and not dfs(i,-t):
            return False
    else:
        return True
if dfs(1,1):
    q=c.count(1)
    print((n-q)*q-m)
else:
    print((n*(n-1)//2)-m)


Measured memory_bytes: 214860
#include <iostream>
#include <cstdio>
#include <algorithm>

typedef long long ll;
#define NMAX 200001
using namespace std;

int main(){
	ll N;
	cin >> N; 
	ll A[NMAX];	
	for(ll i=0; i<N; ++i) scanf("%lld", &A[i]); 
	
	ll count_pair = 0;
	ll j = 0;
	ll sum = 0;
	for (ll i=0; i<N; ++i) {
		while(j<N && ((sum + A[j]) == (sum ^ A[j]))) {
			sum += A[j];
			j++;
		}
		count_pair += j-i;
		if (i == j) ++j;
		else sum -= A[i];
	}	
	cout << count_pair << endl;
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <utility>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <istream>
#include <ostream>
 
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cassert>
 
using namespace std;
 
#define fi first
#define se second
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define rep(i,n) for(ll i=0; i < (n); ++i)
#define rrep(i,n) for(ll i=((n)-1); i >= 0; --i)
 
#define OPLT(T) bool operator<(const T & lop_, const T & rop_)
#define OPEQ(T) bool operator==(const T & lop_, const T & rop_)
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int l[2100], r[2100];

int main() {
	int H, W;
	cin >> H >> W;
	vector<string> S(H);
	rep(i,H) cin >> S[i];

	vector<vector<int> > v(W-1);

	for(int i = 1; i < H; i++) {
		for(int j = 1; j < W; j++) {
			if( (S[i][j]+S[i-1][j] != S[i][j-1]+S[i-1][j-1])
					&& (S[i][j]+S[i][j-1] != S[i-1][j]+S[i-1][j-1]) ) {
				v[j-1].push_back(i);
				//cout << i-1 << "," << j-1 << endl;
			}
		}
	}
	rep(j,W-1) v[j].push_back(H);

	vector<int> indxs(W-1);
	ll res = 0;
	rep(i,H) {
		priority_queue<pii> q;
		rep(j,W-1) {
			while(v[j][indxs[j]] <= i) {
				indxs[j]++;
			}
			q.push(pii(v[j][indxs[j]], j));
		}
		rep(j,W-1) {
			l[j] = r[j] = -1;
		}
		while(q.size()) {
			pii t = q.top(); q.pop();
			ll h = t.fi - i;

			if(t.se == 0 || l[t.se-1] < 0) {
				l[t.se] = t.se;
			}
			else {
				l[t.se] = l[t.se-1];
			}

			if(t.se == W-2 || r[t.se+1] < 0) {
				r[t.se] = t.se;
			}
			else {
				r[t.se] = r[t.se+1];
			}

			r[l[t.se]] = r[t.se];
			l[r[t.se]] = l[t.se];

			res = max(res, h * (r[t.se]-l[t.se]+2));
		}
	}
	res = max(res, (ll)max(H,W));
	cout << res << endl;
}


Measured memory_bytes: 15744
import java.util.*;
import java.math.*;
     
class Main{
    public static void main(String[] args) {
        
        try(Scanner sc = new Scanner(System.in)){

            String str = sc.next();

            String ans = "";
            if(str.equals("ABC")) ans = "ARC";
            else ans = "ABC";
            
            System.out.println(ans);

        }catch(Exception e){
            e.printStackTrace();
        }        
    }
}

Measured memory_bytes: 35632
from collections import defaultdict

N, M = map(int, input().split())
INF = float('inf')

A = [tuple(map(int, input().split())) for _ in range(N)]

def search(sports):
    if not sports:
        return INF

    cnt = [0] * (M + 1)
    for a in A:
        for p in a:
            if p in sports:
                cnt[p] += 1
                break

    ret = max(cnt)
    maxSport = cnt.index(ret)
    sports.remove(maxSport)

    return min(ret, search(sports))

ans = search(set(list(range(1, M + 1))))
print(ans)

Measured memory_bytes: 5464
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = (int)1e5 + 10;

int n;
int32_t main(){_

   cin>>n;
   vector<int> a;
   a.resize(n);

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

   sort(a.begin(), a.end()); 

   int ans = 0;
   for (int i = 0; i < N; ++i)
   {
      int x = lower_bound(a.begin(), a.end(), i) - a.begin();
      ans += (2*x == n);
   }
   
   cout<<ans;

   return 0;
}

Measured memory_bytes: 1024
import sys
input = sys.stdin.readline
from itertools import *
from functools import *
from collections import *
from heapq import heapify, heappop, heappush, heappushpop
from numba import njit

INF = float('inf')
NIL = - 1


N = int(input())
S = input().rstrip()

r_count = S.count('R')
g_count = S.count('G')
b_count = S.count('B')

ret = 0
for i in range(N):
    for d in range(N):
        j = i + d
        k = j + d
        if k >= N:
            break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            ret += 1

ans = r_count * g_count * b_count - ret
print(ans)


Measured memory_bytes: 91724
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<iostream>
#include <algorithm>
using namespace std;

class DICE
{
private:
	const int dice_tem[4][6] = { { 3,2,6,1,5,4 },{ 2,6,3,4,1,5 },
	{ 5,1,3,4,6,2 },{ 4,2,1,6,5,3 } };
	const int sort_num[6] = { 1,4,2,5,3 ,6 };
	static int top;
	static int front;
	const int n = 6;
	int dice_i[6] = { 0 };
	int dice_j[6] = { 0 };
	int ee[6];
	int p;

	void setup() {
		for (int i = 0; i < n; i++) {
			cin >> dice[i];
			dice_i[i] = dice[i];
			ee[i] = dice[i];
		}
		sort(ee,ee+n);
		for (int i = 0, o = 0; i < n && o < 2; i++) {
			ee[o] = ee[i];
			if (ee[m] != ee[i])o++;
		}
		if (m == 0) {
			top = ee[0];
			front = ee[1];
		}
	}

	void dice_sort() {
		for (int d = 0; dice_i[0] != top; d++) {
			for (int i = 0; i < n; i++) {
				dice_j[i] = dice_i[dice_tem[d % 2][i] - 1];
			}
			for (int i = 0; i < n; i++)dice_i[i] = dice_j[i];
		}
		for (p = 0; p < 4; p++) {
			for (int i = 0; i < n; i++) {
				dice_j[i] = dice_i[dice_tem[p][i] - 1];
			}
			if (front == dice_j[0]) break;
		}
		int a = p == 0 ? 3 : p == 1 ? 0 : p == 2 ? 2 : p == 3 ? 1 : -1;
		if (a == 0) {
			for (int i = 0; i < n; i++)sort_dice[i] = dice_i[i];
		}
		else {
			for (int q = 0; q < a; q++) {
				for (int i = 0; i < n; i++)	sort_dice[i] = dice_i[sort_num[i] - 1];
				for (int i = 0; i < n; i++) dice_i[i]=sort_dice[i];
				
			}
		}
	}

public:
	int dice[6];
	int sort_dice[6];
	static int m;
	DICE() {
		setup();
		dice_sort();
		m++;
	}
};
int DICE::m = 0;
int DICE::top = 0;
int DICE::front = 0;
int main() {
	const int n = 6;
	bool flag = true;
	DICE i ;
	DICE j ;
	for (int w = 0; w < n; w++) {
		if (i.sort_dice[w] != j.sort_dice[w])flag = false;
	}
	if (flag == true) {
		cout << "Yes" << endl;
	}
	else if (flag == false) {
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 3160
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <cmath>
#include <cstring>
#include <assert.h>
#include <utility>
#include <tuple>
#include <array>
#include <bitset>
#include <cstdlib>

using int64 = long long;

using namespace std;

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

    int N;
    cin >> N;

    set<string> S;
    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        S.insert(s);
    }
    cout << S.size() << endl;

    return 0;
}



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

int main(void)
{
    long long int ans = 1, tmp, tmp2;
    int n, i,f = 0;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%lld", &tmp);
        tmp2 = ans;
        ans *= tmp;
        if (tmp == 0)
        {
            printf("0");
            return (0);
        }
        if (ans < tmp2)
        {
            f = 1;
        }
        if (ans > 1000000000000000000 || ans < 0)
        {
            f = 1;
        }
    }
    if (f == 1)
        printf("-1");
    else
    printf("%lld", ans);
   return (0);
}


Measured memory_bytes: 1736
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#define rad M_PI/3
#define N 2147483647
#define Max 500000
#define NTL -1
#define min(a,b) ((a>b)?b:a)
#define max(a,b) ((a<b)?b:a)

int main(void)
{
   int h,w,i,j,check=1;
   scanf("%d%d",&h,&w);
   char color[52][52];
   for(i=1;i<h+2;i++){
       for(j=1;j<w+2;j++){
           scanf("%c",&color[i][j]);
       }
   }
   for(i=1;i<h+1;i++){
       for(j=1;j<w+1;j++){
           if(color[i][j]=='#'){
               if(color[i-1][j]=='#'||color[i+1][j]=='#'||color[i][j-1]=='#'||color[i][j+1]=='#'){
                   check=1;
               }else{
                   check=0;
break;
               }
           }
       }
       if(check==0){
           break;
       }
   }
   if(check==1){
       printf("Yes");
   }else{
       printf("No");
   }
   return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)x.size()
//#define int ll

const int N = 2010;
vector<int> g[N];
int dp[N][N], pref1[N], pref2[N], new_dp[N], mx_h[N], sub[N], k;

void dfs(int v, int p = 0) {
	int cnt = 0;
	sub[v] = 1;
	dp[v][0] = 1;
	mx_h[v] = 0;
	for (auto u : g[v]) {
		if (u != p) {
			dfs(u, v);
			//sub[v] += sub[u];
			cnt++;
			if (cnt == 1) {
				for (int i = 0; i <= mx_h[u]; i++) {
					dp[v][i + 1] = 1 + dp[u][i];
				}
			}
			else {
				pref1[0] = dp[v][0];
				for (int i = 1; i <= mx_h[v]; i++) {
					pref1[i] = max(pref1[i - 1], dp[v][i]);
				}
				pref2[0] = dp[u][0];
				for (int i = 1; i <= mx_h[u]; i++) {
					pref2[i] = max(pref2[i - 1], dp[u][i]);
				}
				for (int i = 1; i <= k; i++) {
					new_dp[i] = 0;
				}
				for (int i = 1; i <= min(mx_h[v], k); i++) {
					new_dp[i] = dp[v][i] + pref2[min(mx_h[u], min(i - 1, k - i - 1))];
				}
				for (int i = 1; i <= min(mx_h[u] + 1, k); i++) {
					new_dp[i] = max(new_dp[i], dp[u][i - 1] + pref1[min(mx_h[v], min(i, k - i))]);
				}
				for (int i = 1; i <= max(mx_h[v], mx_h[u] + 1); i++) {
					dp[v][i] = max(dp[v][i], new_dp[i]);
				}
			}
			mx_h[v] = max(mx_h[v], mx_h[u] + 1);
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(1);
	int ans = n;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= min(mx_h[i], k); j++) {
			ans = min(ans, n - dp[i][j]);
		}
	}
	cout << ans << '\n';
}	

Measured memory_bytes: 15616
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <memory>
#include <string>

#include <algorithm>
#include <complex>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
#endif

#define ITER(c)         __typeof__((c).begin())
#define FOREACH(it, c)  for (ITER(c) it=(c).begin(); it != (c).end(); ++it)
#define RITER(c)        __typeof__((c).rbegin())
#define RFOREACH(it, c) for (RITER(c) it=(c).rbegin(); it != (c).rend(); ++it)
#define REP(i, n)       REPEAT(i, 0, n)
#define REPEAT(i, k, n) for (int i = (k); i < (n); ++i)
#define REVREP(i, n)    for (int i = ((n)-1); i >= 0; --i)
#define FIND(c, n)      std::find((c).begin(), (c).end(), (n));
#define BSEARCH(c, n)   std::binary_search((c).begin(), (c).end(), (n))
#define LLPOW(p1,p2)    ((ll)pow((double)(p1), (int)p2))
#define ESIZEOF(A)      (sizeof(A)/sizeof((A)[0]))
#define MIN(p1,p2)      (((p1)<(p2))?(p1):(p2))
#define MAX(p1,p2)      (((p1)>(p2))?(p1):(p2))
#define CIN_NO_SYNC     do { cin.tie(0); ios_base::sync_with_stdio(false); } while(0)
#define GETSTR(p)       fgets((p), sizeof(p), stdin)
#define CHOMP(p)        do{ char *_q = (p) + strlen(p)-1; if(*_q == '\n') *_q = 0; } while(0)

#define X real()
#define Y imag()
typedef double D;
typedef complex<double>P;
#define EPS (1e-9)

bool iscross(P &p1, P &p2, P &p3, P &p4){
    double f1 = p2.X - p1.X;
    double g1 = p2.Y - p1.Y;
    double f2 = p4.X - p3.X;
    double g2 = p4.Y - p3.Y;
    double det = f2 * g1 - f1 * g2;
    if(abs(det) < EPS) return false;
    return true;
}

int main(){
    int n;
    cin >> n;
    REP(i,n){
        double x1, y1, x2, y2, x3, y3, x4, y4;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
        P p1(x1,y1), p2(x2,y2), p3(x3,y3), p4(x4,y4);
        if(!iscross(p1,p2,p3,p4)){
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1224
import sys
N = int(input())
A = [list(map(int,input().split())) for x in range(N)]

A_ = sorted(A,key=lambda x: x[1])
Sum = 0
for x in A_:
    Sum += x[0]
    if Sum > x[1]:
        print("No")
        sys.exit()
else:
    print("Yes")

Measured memory_bytes: 55192
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i,n) for(int i=1; i<=(n); ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define sz(v) (int)v.size()
#define pb push_back

using namespace std;
int N,M,Q;
int P[505][505];
int l,r;
int p,q;

int main(){
    cin >> N >> M >> Q;
    rep(i,M){
        cin >> l >> r;
        P[l][r]++;
    }
    
    rep1(i,N) rep1(j,N-1) P[i][j+1] += P[i][j];
    
    rep(i,Q){
        cin >> p >> q;
        int ans = 0;
        for(int i = p; i <= q; ++i) ans += P[i][q]-P[i][p-1];
        cout << ans << endl;
    }
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REPR(i,n) for (int i=(int)(n)-1;i>=0;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
#define tpl(...) make_tuple(__VA_ARGS__)
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1);
const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};
typedef long long ll;
typedef pair<int,int> pii;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename Ch,typename Tr,typename C,typename=decltype(begin(C()))>basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>&os,
const C& c){os<<'[';for(auto i=begin(c);i!=end(c);++i)os<<(i==begin(c)?"":" ")<<*i;return os<<']';}
template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';}
template<int N,class Tp>void output(ostream&,const Tp&){}
template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);}
template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';}
template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20];
int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);}
template<class T>void outputs(T t){output(t);}
template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);}
template<class T>void output(T *a,int n){REP(i,n)cout<<a[i]<<(i!=n-1?',':'\n');}
template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);}
template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;);
if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;}
template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);}
template<class T>bool inputs(T *a, int n) { REP(i,n) if(!input(a[i])) return 0; return 1;}

int x[4];
string ans;
void rec(int index, int sum, string s)
{
  if (index == 4)
  {
    if (sum == 7) {
      ans = s;
    }
    return;
  }
  rec(index+1, sum+x[index], s + "+" + to_string(x[index]));
  rec(index+1, sum-x[index], s + "-" + to_string(x[index]));
}
int main() {
  string s;
  while (cin >> s) {
    REP(i,4) {
      x[i] = s[i] - '0';
    }
    rec(1, x[0], to_string(x[0]));
    cout << ans + "=7" << endl;
  }
}


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

int main(){
    int  n;
    long long d;
    int ans = 0;
    cin >> n >> d;

    rep(i, n){
        long long x, y;
        cin >> x >> y;
        if(x*x + y*y <= d*d) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
using namespace std;
int main(void){
#define MAX 10100
    int n; //販売されるアイスクリームの総数
    int c[MAX]; //アイスクリームの種類

    while(true){
        cin >> n;
        if(n == 0) break;
        
        int k[10] = {0}; //種類を集計
        for(int i = 0; i < n; i++){
            cin >> c[i];
            
            if(c[i] == 0) k[0]++;
            if(c[i] == 1) k[1]++;
            if(c[i] == 2) k[2]++;
            if(c[i] == 3) k[3]++;
            if(c[i] == 4) k[4]++;
            if(c[i] == 5) k[5]++;
            if(c[i] == 6) k[6]++;
            if(c[i] == 7) k[7]++;
            if(c[i] == 8) k[8]++;
            if(c[i] == 9) k[9]++;
        }

        for(int i = 0; i < 10; i++){
            if(k[i] == 0){
                cout << '-' << endl;
            }
            if(k[i] != 0){
                int s = k[i];
                for(int j = 1; j <= s; j++){
                    cout << '*';
                }
                cout << endl;
            }
            // if(k[i] == 0) cout << '-';
            // else{
            //     for(int j = 1; j < k[i]; j++)
            //         cout << '*';
            // }
            // cout << endl;
        }
    }
}



Measured memory_bytes: 3104
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

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

int main(){
    string b; cin>>b;
    if(b=="A") cout << "T" << endl;
    if(b=="T") cout << "A" << endl;
    if(b=="C") cout << "G" << endl;
    if(b=="G") cout << "C" << endl;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
  var a, b, c int
  fmt.Scan(&a, &b, &c)
  
  for i := 0; i < b; i++ {
    if a * i % b == c {
      fmt.Println("YES")
      return
    }
  }
  fmt.Println("NO")
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
///////////////////////////////////////////////////////////////////////////////////////////////////////
const int maxn=1e5+10;
const int maxm=1e2+10;
long long int dp[maxn][maxm];
int n;
int k;
int w[maxn];
int u[maxn];
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	int res=0;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>u[i];
		res+=u[i];
	}
	for(int i=0;i<=res;i++){
		if(i==0){
			dp[0][i]=0;
		}
		else{
			dp[0][i]=1e9+10;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=res;j>=0;j--){
			if(j>=u[i]){
		dp[i][j]=min(dp[i-1][j-u[i]]+w[i],dp[i-1][j]);
	}
	else{
		dp[i][j]=dp[i-1][j];
	}
		}
	}
	int ans=0;
	for(int i=0;i<=res;i++){
		if(dp[n][i]<=k){
			ans=i;
		}
	}
	cout<<ans;
	return 0;
	
}


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

int v[1000], w[1000], dp[105][10010];

int main(void) {
  int N, W;
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> N >> W;
  for (int i = 0; i < N; i++) cin >> v[i] >> w[i];

  for (int i = 0; i < N; i++) {
    for (int j = 1; j <= W; j++) {
      if (j - w[i] >= 0) {
        if (!i) {
          dp[i][j] = v[i];
        } else {
          dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
        }
      } else {
        if (i) dp[i][j] = dp[i-1][j];
      }
      // cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << endl;

    }
  }

  cout << dp[N-1][W] << endl;
  return 0;
}

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

limit = 0
tmp = A[0]
for a in A[1:]:
   limit = max(limit, a - tmp)
   tmp = min(tmp, a)

ans = [0] * N
maximum = A[-1]
ans[-1] = maximum
for i in range(N - 2, -1, -1):
    ans[i] = maximum - limit #これより安くする必要がある
    maximum = max(maximum, A[i])

tmp = 0
for i in range(N - 1):
    tmp += max(0, ans[i] - A[i] + 1)

# print (A)
# print (ans)
print (tmp)

Measured memory_bytes: 15020
import java.io.*;
import java.math.*;
import java.util.*;
public class Main { 

	public static void main(String[] args) { 
		Scanner input = new Scanner(System.in);
		int X = input.nextInt();
		int t = input.nextInt();
		System.out.println(Math.max(0, X-t));
	}
}

Measured memory_bytes: 21332
import java.util.*;

class Main {
	Scanner sc;
	int N, T;
	List<Dish> D;
	// 個数,時間
	int[][] dp;
	
	static class Dish {
		int A, B;
		Dish(int a, int b) {
			A = a;
			B = b;
		}
	}
	
	void calc() {
		sc = new Scanner(System.in);
		N = sc.nextInt();
		T = sc.nextInt();
		D = new ArrayList<>();
		for (int i = 0; i < N; i++) D.add(new Dish(sc.nextInt(), sc.nextInt()));
		D.sort(Comparator.comparingInt(d -> d.A));
		
		dp = new int[N+1][6000];
		int max = Integer.MIN_VALUE;
		for (int i = 1; i < N+1; i++) {
			Dish d = D.get(i-1);
			for (int j = 0; j < 6000; j++) {
				if (j >= d.A && j-d.A < T) {
					dp[i][j] = Math.max(dp[i-1][j - d.A] + d.B, dp[i-1][j]);
				} else {
					dp[i][j] = dp[i-1][j];
				}
				max = Math.max(max, dp[i][j]);
			}
		}
		System.out.println(max);
	}

	public static void main(String[] args) {
		new Main().calc();
	}
}


Measured memory_bytes: 124712
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
int A[100000], B[100000];
struct UnionFind {
	vector<int> par;
	vector<int> rank;
	vector<int> cmp;
	int size;
	UnionFind(int n) :size(n) {
		par.resize(size);
		rank.resize(size);
		cmp.resize(size);
		for (int i = 0; i < size; i++) {
			par[i] = i;
			rank[i] = 0;
			cmp[i] = 1;
		}
	}
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (rank[x] < rank[y]) {
			par[x] = y;
			cmp[y] += cmp[x];
		}
		else {
			par[y] = x;
			cmp[x] += cmp[y];
			if (rank[x] == rank[y]) rank[x]++;
		}
	}
	int find(int x) {
		if (par[x] == x) return x;
		return par[x] = find(par[x]);
	}
	bool same(int x, int y) {
		x = find(x);
		y = find(y);
		return x == y;
	}
};
ll ans[100000];
int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> A[i] >> B[i];
		A[i]--;
		B[i]--;
	}
	ans[M - 1] = (ll)N*(N - 1) / 2;
	UnionFind U(N);
	for (int i = M - 1; i > 0; i--) {
		int x = U.find(A[i]);
		int y = U.find(B[i]);
		if (x != y) {
			ans[i - 1] = ans[i] - (ll)U.cmp[x] * U.cmp[y];
			U.unite(x, y);
		}
		else {
			ans[i - 1] = ans[i];
		}
	}
	for (int i = 0; i < M; i++) {
		cout << ans[i] << endl;
	}
}


Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll i,j,k,z,n=0,m,s=0,x=0;
	string str , arr;
	cin>>str>>arr;
	char pp[100];
	for(i=0;i<str.size();i++)
	{n=0;s=0;
		for(j=i;j<str.size();j++)
		{
			pp[n]=str[j];
			n=n+1;
		}
		for(k=0;k<i;k++)
		{
			pp[n]=str[k];
			n=n+1;
		}
		for(z=0;z<str.size();z++)
		{
			if(pp[z]==arr[z]){s=s+1;
			}
		}
		if(s==str.size())
		{x=1;break;
		}
	}
	
	if(x==1)
	{cout<<"Yes";
	}
	else
	{cout<<"No";
	}
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
	int h,m,s,S;
	scanf("%d",&S);
	h=S/3600;
	S=S%3600;
	m=S/60;
	s=S%60;
	printf("%d:%d:%d\n",h,m,s);
	
	return 0;
}

Measured memory_bytes: 592
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

#階乗#
lim = 2*10**5   #必要そうな階乗の限界を入力
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod

#階乗の逆元#
fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	if n < r or n < 0 or r < 0:
		return 0
	else:
		return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod

N, K = MAP()

if N == K:
	for i in range(1, N+1):
		print(i if i == 1 else 0)
	exit()

for i in range(1, K+1):
	blue = C(K-1, i-1) #青いボールをi個の塊に分ける
	red = (C(N-K-1, i-2) + 2*C(N-K-1, i-1) + C(N-K-1, i))%mod #赤いボールをi-1、i、i+1個の塊に分ける(i個の場合は2パターン)
	print((blue*red)%mod)


Measured memory_bytes: 26144
#include <stdio.h>

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

Measured memory_bytes: 1728
#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const ll INF = 1e18;
/* テンプレートここまで */

int main() {
  ll n,x; cin >> n >> x;
  vector<ll> m(n); 
  REP(i, n){
    cin >> m[i];
    x -= m[i];
  }
  sort(ALL(m));
  cout << n + x/m[0] << endl;
} 

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

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

const ll INF = LLONG_MAX;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

#define int long long

inline void my_io() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	cout << fixed << setprecision(16);

	//cout << setprecision(10) << scientific << ans << endl;
}

signed main() {
	ll n, qq, a, b, p, x;

	cin >> n >> qq;

	vector<vector<ll>> G(n);
	vector<ll> ans(n, 0);

	REP(i, n - 1) {
		cin >> a >> b;
		G[a - 1].push_back(b - 1);
		G[b - 1].push_back(a - 1);
	}

	REP(i, qq) {
		cin >> p >> x;

		ans[p - 1] += x;
	}

	queue<ll> q;
	vector<ll> used(n, false);
	q.push(0);
	used[0] = true;

	while (!q.empty()) {
		ll now = q.front();
		q.pop();
		REP(j, G[now].size()) {
			ll next = G[now][j];
			if (used[next]) {
				continue;
			}
			used[next] = true;
			ans[next] += ans[now];
			q.push(next);
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 19440
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
#include<bitset>
#include<cstdlib>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

#define POS(x) cout<<((x)?"POSSIBLE":"IMPOSSIBLE")<<endl;
#define Pos(x) cout<<((x)?"Possible":"Impossible")<<endl;
#define YES(x) cout<<((x)?"YES":"NO")<<endl;
#define Yes(x) cout<<((x)?"Yes":"No")<<endl;
#define yes(x) cout<<((x)?"yes":"no")<<endl;


int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  string s;
  cin >> s;
  sort(begin(s), end(s));
  Yes(s[0] == s[1] && s[2] == s[3] && s[1] != s[2]);
  return 0;
}


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



 int  main() {
      int n;
      cin>>n;
      int a[n];
      int cnt[n+1]={0};
      for(int i=0;i<(n-1);i++){
          cin>>a[i];
          cnt[a[i]]++;
      }
      
      for(int i=1;i<=n;i++){
          cout<<cnt[i]<<endl;
      }
      
      
    
    return 0;
}

Measured memory_bytes: 5236
#include <iostream>

using namespace std;

int main() {
  int r,b ;
  int cnt = 1;

  while(cin >> r >> b , r + b != 0 ) {
   if ( r < b ) {
   cout << r << " " << b << endl;
       
} else {
   cout << b << " " << r << endl;
 }
  }
  
  
}

Measured memory_bytes: 3076
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long a = in.nextLong();
        long b = in.nextLong();
        long c = in.nextLong();
        long k = in.nextLong();
        long ans = Math.min(k, a);
        k -= ans;
        k -= b;
        if(k>0) {
            ans -= Math.min(k, c);
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 35780