akhauriyash/Code-Regression huggingface dataset:
#include"bits/stdc++.h"
using namespace std;
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for (int i = (b - 1); i >= a; i--)
#define RREP(i, n) RFOR(i, 0, n)
#define rep(i, a, b) for (auto i = a; i < b; i++)
#define rrep(i, a, b) for (auto i = a; i > b; i--)
#define fs first
#define sc second
//typedef pair<int, int> P;


int M, T, P, R;


class Team
{
public:
	int id;
	int score = 0;
	int time = 0;
	vector<int> pena = vector<int>(P);

	bool operator<(const Team & a)const
	{
		if (score == a.score)
		{
			if (time == a.time)
			{
				return id > a.id;
			}
			return time < a.time;
		}
		return score > a.score;
	}

};


bool solve()
{
	cin >> M >> T >> P >> R;
	if (M == 0)return false;

	vector<Team> tL(T);
	REP(i, T)
	{
		tL[i].id = i + 1;
	}

	REP(i, R)
	{
		int m, t, p, j;
		cin >> m >> t >> p >> j;
		--t; --p;
		if (j == 0)
		{
			tL[t].score++;
			tL[t].time += m + tL[t].pena[p];
		}
		else
		{
			tL[t].pena[p] += 20;
		}
	}

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

	cout << tL[0].id;
	FOR(i, 1, T)
	{
		if (tL[i].score == tL[i - 1].score && tL[i].time == tL[i - 1].time)
		{
			cout << "=";
		}
		else
		{
			cout << ",";
		}
		cout << tL[i].id;
	}
	cout << endl;

	return true;
}


int main()
{
	while (solve())
	{

	}

	return 0;
}


Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(int i = (m); i <= (n); i++)
#define zep(i,m,n) for(int i = (m); i < (n); i++)
#define rrep(i,m,n) for(int i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(int i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	ll n; cin >> n;
	ll cnt[n]; memset(cnt, 0, sizeof(cnt));
	zep(i, 1, n){
		ll a; cin >> a;
		a--;
		cnt[a]++;
	}
	
	zep(i, 0, n){
		print(cnt[i])
	}
	
	return 0;
}

Measured memory_bytes: 5232
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<string>
#define ll long long
#define mod 1000000007
using namespace std;
ll a[27];
string s;
int main(void)
{
    int n;
    ll ans;
    scanf("%d",&n);
    cin>>s;
    for(int i=0;i<27;i++)
        a[i] = 1;
    for(int i=0;i<n;i++)
        a[s[i]-'a']++;
    ans = 1;
    for(int i=0;i<27;i++)
        ans = (ans*a[i]) % mod;

    printf("%lld\n",ans-1);
    return 0;
}


Measured memory_bytes: 1020
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h> // uint64_t

#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) > (b) ? (b) : (a))

int get_int(void) {
  int num;
  scanf("%d", &num);
  return num;
}

int get_int2(int *a1, int *a2) {
  scanf("%d %d", a1, a2);
  return 0;
}
#define NUM_MAX 200000
#define DIVISOR 1000000007

static int64_t factorial[NUM_MAX+1];
static int64_t inv_factorial[NUM_MAX+1];

struct pair {
    int x;
    int y;
};

struct pair gcdext(int a, int b) {
    if(a==0) { return (struct pair){0, 1}; }
    struct pair p = gcdext(b%a, a);
    return (struct pair){ p.y - (b/a)*p.x, p.x };
}

void init_combi(void) {
    factorial[0] = factorial[1] = 1;
    inv_factorial[0] = inv_factorial[1] = 1;
    int i;
    for(i = 2; i <= NUM_MAX; i++) {
        factorial[i] = (factorial[i-1]*i)%DIVISOR;
        struct pair p = gcdext(i, DIVISOR);
        int inv = (p.x+DIVISOR)%DIVISOR;
        inv_factorial[i] = (inv_factorial[i-1]*inv)%DIVISOR;
    }
    return;
}

int64_t get_combi(int n, int k) {
    int64_t res = 1;
    res = (res * factorial[n])%DIVISOR;
    res = (res * inv_factorial[n-k])%DIVISOR;
    res = (res * inv_factorial[k])%DIVISOR;
    return res;
}

int64_t get_homo(int n, int k) {
    return get_combi(n+k-1, k);
}

int main(void) {
    int num, k;
    get_int2(&num, &k);
    if(k >= num-1) k = num-1;
    init_combi();

    int i;
    int64_t ans = 0;
    for(i = 0; i <= k; i++) {
        int64_t res = 1;
        // i: # of zero
        res = (res * get_combi(num, i))%DIVISOR;
        res = (res * get_homo(num-i, i))%DIVISOR;
        ans = (res + ans)%DIVISOR;
    }
    printf("%d\n", (int)ans);
    return 0;
}


Measured memory_bytes: 3328
package main

import (
	"fmt"
	"math"
)

func main() {
	var n, d int
	fmt.Scan(&n, &d)


	x := make([][]int, n)
	for i:=0;i<n;i++{
		x[i] = make([]int, d)
		for j :=0;j<d;j++ {
			fmt.Scan(&x[i][j])
		}
	}
	ans := 0

	for i := 0; i < n; i++ {
		for j := i +1; j < n;j++{
			sq := 0
			for k :=0;k<d;k++ {
				diff :=x[i][k] - x[j][k]
				sq += diff * diff
			}

			s := int(math.Sqrt(float64(sq)+0.5))
			if s * s == sq {
				ans++
			}
		}
	}
	fmt.Println(ans)
}
func abs(n int) int {
	y := n >> 63
	return (n ^ y) - y
}


Measured memory_bytes: 1784
import java.util.Scanner;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    while(true){
      String str = sc.next();
      if(str.equals("-")) break;
      int m = sc.nextInt();
      for(int i=0;i<m;i++){
        int h = sc.nextInt();
        str = str.substring(h, str.length()) + str.substring(0, h);
      }
      System.out.println(str);
    }
    sc.close();
  }
}


Measured memory_bytes: 26388
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	long long a,b,c,d;
	scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
	long long x1=a*c;
	long long x2=a*d;
	long long x3=b*c;
	long long x4=b*d;
	printf("%lld",max(x1,max(x2,max(x3,x4))));
	return 0;
}

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


dp = [[[0]*(55) for i in range(3000)]for i in range(55)]
dp[0][0][0] = 1

for i in range(n):
  for j in range(n*a):
    for k in range(n):
      dp[i+1][j][k] += dp[i][j][k]
      dp[i+1][j+x[i]][k+1] += dp[i][j][k]
      
    
ans = 0
for k in range(1,n+1):
  ans += dp[n][k*a][k]
print(ans)

Measured memory_bytes: 158176
S = input()
ans=0
if S[0] == S[1]:
    if S[2] == S[3]and S[0]!=S[2]:
        print("Yes")
        ans=1
elif S[0] == S[2]:
    if S[1] == S[3]and S[0] != S[1]:
        print("Yes")
        ans=1
elif S[0] == S[3]:
    if S[1] == S[2]and S[0] != S[2]:
        print("Yes")
        ans=1

if ans==0:
    print("No")


Measured memory_bytes: 3064
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        var temp = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        long n = temp[0];
        long skillLimit = temp[1];
        List<long> monsterHPs = Console.ReadLine().Split(' ').Select(s => long.Parse(s)).ToList();
        monsterHPs.Sort();

        if(skillLimit >= monsterHPs.Count)
        {
            System.Console.WriteLine(0);
            return;
        }

        for (long i = 0; i < skillLimit; i++)
        {
            monsterHPs.RemoveAt(monsterHPs.Count - 1);
        }

        System.Console.WriteLine(monsterHPs.Sum());
    }
}

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

void solve() {
	map<int, int> cnt1, cnt2;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		if (i % 2 == 1) {
			cnt1[x]++;
		}
		else {
			cnt2[x]++;
		}
	}	
	int mx1 = 0, mx2 = 0, mx11 = 0, mx22 = 0;
	int x1 = -1, x2 = -1;
	for (auto x : cnt1) {
		if (x.second >= mx1) {
			mx11 = mx1;
			x1 = x.first;
			mx1 = x.second;
		}
		else if (x.second > mx11) {
			mx11 = x.second;
		}
	}
	for (auto x : cnt2) {
		if (x.second >= mx2) {
			mx22 = mx2;
			x2 = x.first;
			mx2 = x.second;
		}
		else if (x.second > mx22) {
			mx22 = x.second;
		}
	}
	if (x1 != x2) cout << n - (mx1 + mx2);
	else {
		cout << n - max(mx1 + mx22, mx11 + mx2);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	for (int i = 1; i <= t; i++) {
		solve();
	}
}

Measured memory_bytes: 8268
#include<bits/stdc++.h>
using namespace std;
int a[105];
int main()
{
	int n,sum=0;
	cin>>n;
	for(int i=0;i<n;i++)
		{
			cin>>a[i];
			sum+=a[i];
		 } 
	sort(a,a+n);
	int sum1=0;
	if(n%2==0)
	{
		for(int i=1;i<n;i+=2)
		    sum1+=a[i];
		cout<<2*sum1-sum<<endl;}
	else {
		for(int i=0;i<n;i+=2)
		   sum1+=a[i];
		cout<<2*sum1-sum<<endl;
}
	return 0;
 } 

Measured memory_bytes: 256
// package app;

import java.math.BigDecimal;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {

    public static void main(final String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);

        long N = sc.nextLong();
        String text = sc.next();

        String leftHalfStr = text.substring(0, text.length() / 2 );
        String rightHalfStr = text.substring(text.length() / 2 , text.length());

        System.out.println(leftHalfStr.equals(rightHalfStr) ? "Yes" : "No");
    }
}

Measured memory_bytes: 23124
N=int(input())
V=list(map(int,input().split()))

from collections import Counter
V_1=V[::2]
V_2=V[1::2]

V_1_counter=Counter(V_1).most_common()
V_2_counter=Counter(V_2).most_common()
# print(V_1_counter,V_2_counter)

V_1_max_1 = V_1_counter[0]
V_1_max_2=(0,0)
if len(V_1_counter)>1:
    V_1_max_2 = V_1_counter[1]
    
V_2_max_1=V_2_counter[0]
V_2_max_2=(0,0)
if len(V_2_counter)>1:
    V_2_max_2 = V_2_counter[1]
    
if V_1_max_1[0] != V_2_max_1[0]:
    ans = N-V_1_max_1[1]-V_2_max_1[1]
    
else:
    ans=N-max(V_1_max_1[1]+V_2_max_2[1],V_1_max_2[1]+V_2_max_1[1])
    
print(ans)

Measured memory_bytes: 95700
# encoding:utf-8

def main():
	N, M = list(map(int, input().split()))
	prefs = [list(map(int, input().split())) for _ in range(N)]

	game_list = [i for i in range(1, M + 1)]

	tmp = 10 ** 10
	for i in range(M):
		max_game, idx = maxGame(prefs, game_list, M)
		tmp = min(tmp, max_game)
		prefs = removeGame(prefs, idx + 1)
	print(tmp)

def removeGame(prefs, idx):
	for i in range(len(prefs)):
		prefs[i].remove(idx)
	return(prefs)

def maxGame(prefs, game_list, M):
	counter = [0 for _ in range(M)]
	for i in range(len(prefs)):
		counter[prefs[i][0] - 1] += 1
	return([max(counter), counter.index(max(counter))])

if __name__ == '__main__':
	main()

Measured memory_bytes: 4300
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,x,n) for(int i=(x);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define int long long
using namespace std;
const int MOD=1e9+7;
const int INF=1e10;
template<typename T> void cmax(T &a, T b) {a = max(a, b);}
template<typename T> void cmin(T &a, T b) {a = min(a, b);}

int extgcd(int a,int b,int& x,int& y){
  int g=a;
  if(b!=0){
    g=extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }else{
    x=1;y=0;
  }
  return g;
}

signed main(){
  int a,b;
  cin>>a>>b;
  int x,y;
  int GCD=extgcd(a,b,x,y);
  cout<<x<<' '<<y<<endl;
  return 0;
}



Measured memory_bytes: 3100
#include <stdio.h>
#include <string.h>
#define LEN 100005

typedef struct pp{
	char name[100];
	int t;
}P;

P Q[LEN+1];
int head, tail, n;

void enqueue(P x);
P dequeue();
int min(int a, int b);

int main(){
  int elaps = 0, c;
  int i, q;
  P u;
  scanf("%d %d", &n, &q);

  for ( i = 1; i <= n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
	head = 1;
	tail = n+1;
	
	while(head != tail){
		u = dequeue();
		c = min(q, u.t);
		u.t -= c;
		elaps += c;
		if(u.t > 0)enqueue(u);
		else printf("%s %d\n", u.name, elaps);
	}
	
  return 0;
}

void enqueue(P x){
	Q[tail] = x;
	tail = (tail+1)%LEN;
}

P dequeue(){
	P x = Q[head];
	head = (head+1)%LEN;
	return x;
}

int min(int a, int b){
	if(a < b)return a;
	else return b;
}


Measured memory_bytes: 11884
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  rep(i,n) {
    cin >> v.at(i);
  }
  map<int,int>memo1,memo2;
  rep(i,n){
    if(i%2==0){
      memo1[v.at(i)]++;
    }
    else{
      memo2[v.at(i)]++;
    }
  }
  int g1=0;
  int g2=0;
  int k1=0;
  int k2=0;
  int ga,gb,ka,kb;
  for (auto p:memo1) {
    auto ke = p.first;
    auto va = p.second;
    if(g1<va&&g2<va){
      g2=g1;
      g1=va;
      gb=ka;
      ga=ke;
    }
    else if(g1>=va&&g2<va){
      g2=va;
      gb=ke;
    }
  }
  for (auto p:memo2) {
    auto ke = p.first;
    auto va = p.second;
    if(k1<va&&k2<va){
      k2=k1;
      k1=va;
      kb=ka;
      ka=ke;
    }
    else if(g1>=va&&g2<va){
      g2=va;
      gb=ke;
    }
  }
  if(ga!=ka){
    cout<<n-g1-k1<<endl;
  }
  else{
    if(g1+k2<g2+k1){
      cout<<n-g2-k1<<endl;
    }
    else{
      cout<<n-g1-k2<<endl;
    }
  }
}

Measured memory_bytes: 5376
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <set>
#define INF 1000000000
#define LLINF 2000000000000000
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define LOOP(i,N) for(int i=0;i<N;i++)
#define LOOP1(i,N) for(int i=1;i<=N;i++)
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
// #define int long long

signed main(){
  int n;
  int x[100];
  cin >> n;
  LOOP(i,n){
    cin >> x[i];
  }
  int ans = INF;
  LOOP(i,100){
    int tmp = 0;
    LOOP(j,n){
      tmp += (i-x[j])*(i-x[j]);
    }
    ans = min(tmp, ans);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
use std::vec::Vec;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
    let (a, p) = {
      let v:Vec<i64> = read_vec();
      (v[0], v[1])
    };

    println!("{}", (3 * a + p) / 2)

}


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

typedef vector <int> VI;

int main( void )
{
	int n, no, mm, ss;
	while ( cin >> n && n )
	{
		VI no_list( n );
		VI time_list( n );

		for ( int j = 0; j < n; j++ )
		{
			cin >> no;
			int sum = 0;
			for ( int i = 0; i < 4; i++ )
			{
				cin >> mm >> ss;
				ss += mm * 60;
				sum += ss;
			}
			no_list[j] = no;
			time_list[j] = sum;
		}

		for ( int i = 0; i < n-1; i++ )
		{
			for ( int j = i+1; j < n; j++ )
			{
				if ( time_list[i] > time_list[j] )
				{
					swap( time_list[i], time_list[j] );
					swap( no_list[i], no_list[j] );
				}
			}
		}

		cout << no_list[0] << endl;
		cout << no_list[1] << endl;
		cout << no_list[n-2] << endl;
	}
	return 0;
}

Measured memory_bytes: 940
N, X = map(int, input().split())
L = list(map(int, input().split()))

L_cum = [0] * (N+1)
flag = 0
for i in range(N):
    L_cum[i+1] = L_cum[i] + L[i]
    if L_cum[i+1] > X:
        ans = i + 1
        flag = 1
        break
if flag == 1:
    print(ans)
else:
    print(N+1)


Measured memory_bytes: 38384
#include<stdio.h>

int main(){
  int a, b, c,count;

  while(1){
    if(scanf("%d%d",&a,&b) == EOF) break;
    c = a + b;
    count = 0;
    while(c > 0){
      c = c / 10;
      count++;
    }
    printf("%d\n",count);
  }

  return 0;

}

Measured memory_bytes: 600
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
typedef long long ll;
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    int hoge=0;
    hoge = a - 2*b;
    if(hoge<=0) cout<<"0"<<endl;
    else cout<<hoge<<endl;

    return 0;
}

Measured memory_bytes: 888
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <climits>
#include <complex>
#include <numeric>
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RREP(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 RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)
#define ALL(c) (c).begin(), (c).end()

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > pipii;
typedef vector<int> vi;

const int INF = 1e9;
const int MOD = 1e9+7;

int main(void){
	int n;
	cin >> n;
	ll ans = 0;
	ll res = INF;
	int f = 1;
	REP(i, n) {
		ll a, b;
		cin >> a >> b;
		if(a != b) f = 0;
		ans += a;
		if(a > b) {
			res = min(res, b);
		}
	}
	if(f) cout << 0 << endl;
	else cout << ans - res << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define REP(i, n) for (signed long long i = 0; i < (n); i++)
#define MOD 1000000007
#define bitcnt(a) (ll) __builtin_popcount((a))
using namespace std;
typedef long long ll;

map<ll, ll> m;
int main() {
  ll n;
  cin >> n;
  vector<ll> v;
  REP(i, n) {
    ll h;
    cin >> h;
    v.pb(h);
  }
  ll cnt = 0, ret = 0;
  for (auto &a : v) {
    cnt += a;
    if (cnt == 0)
      ret++;
    if (m[cnt] > 0) {
      ret += m[cnt];
    }
    m[cnt]++;
  }
  cout << ret << endl;
}


Measured memory_bytes: 14320
import math

A,B,H,M=tuple(map(int,input().split()))

U=(M/60)*2*math.pi
V=(H*60+M)/(12*60)*2*math.pi
W=abs(U-V)

if W>=math.pi:
    W=2*math.pi-W

print(math.sqrt(A*A+B*B-2*A*B*math.cos(W)))


Measured memory_bytes: 62576
fun main(args: Array<String>) {
    val sc = java.util.Scanner(System.`in`)
    val n = sc.nextInt()
    val m = sc.nextInt()
    val a = LongArray(n + 1)
    sc.asSequence().take(m).map(String::toInt).forEach { a[it] = -1L }

    if (a[0] != -1L) a[0] = 1L
    if (a[1] != -1L) a[1] = 1L

    for (i in 2..n) {
        if (a[i] == -1L) {

        } else if (a[i - 1] == -1L) {
            if (a[i - 2] == -1L) {
                println(0)
                return
            }
            a[i] = a[i - 2]
        } else if (a[i - 2] == -1L) {
            a[i] = a[i - 1]
        } else {
            a[i] = (a[i - 2] + a[i - 1])  % 1000000007
        }
    }

    if (a.last() == -1L) {
        println(0)
        return
    }

    println(a.last())
}


Measured memory_bytes: 48444
#include<bits/stdc++.h>
using namespace std;
map<int,int>mp;
void callme()
{
  for(int i=1;i<=100;i++)
  {
  	for(int j=1;j<=100;j++)
  	{
  		for(int k=1;k<=100;k++)
  		{
  		   int temp=(i*i)+(j*j)+(k*k)+(i*j)+(j*k)+(k*i);
  		    //cout<<temp<<" ";
           // cout<<temp<<" ";
            /*unordered_set<int>s;
  			s.insert(i);
  			s.insert(j);
  			s.insert(k);
  			int count=s.size();
  			s.clear();
  			if(count==1)
  				mp[temp]=1;
  			else if(count==2)
  				mp[temp]=3;
  			else if(count==3)
  				mp[temp]=6;*/
  				mp[temp]++;
  		}
  	}
  }
 /* for(auto it=mp.begin();it!=mp.end();it++)
  cout<<it->first<<" "<<it->second<<endl;*/
}
int main()
{
  int n;
  cin>>n;
  callme();
  for(int i=1;i<=n;i++)
  {
     if(mp.find(i)!=mp.end())
     	cout<<mp[i]<<endl;
     else
     	cout<<0<<endl;
  }
}

Measured memory_bytes: 5372
//AUTHOR: RAVAN_2070
//PUNE INSTITUTE OF COMPUTER TECHNOLOGY
//Atcoder Educational DP
//M-Candies
/*
    I ♥ CLARICE STARLING

    EXPLAINATION BELOW->
    Dp  
*/
//Iterative Solution
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
#define MOD7 1000000007
const ll INF=(ll)1e18+5;
void solve()
{
   int n,k,i,j;cin>>n>>k;
   int ps[k+2][n],dp[k+1][n],A[n];
   
   fo(i,0,n)cin>>A[i];
   
   fo(j,0,n)ps[0][j]=0;
   foe(i,0,k){dp[i][n-1]=((i<=A[n-1])?1:0);ps[i+1][n-1]=ps[i][n-1]+dp[i][n-1];}
   for(j=n-2;j>=0;j--)
   {
       for(i=0;i<=k;i++)
       {
           int low,high;
           low=max(0,i-A[j]);high=i;
           dp[i][j]=(ps[high+1][j+1]-ps[low][j+1]+MOD7)%MOD7;
           ps[i+1][j]=(ps[i][j]+dp[i][j])%MOD7;
       }
       
       
   }
   cout<<dp[k][0]%MOD7<<"\n";

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



Measured memory_bytes: 78336
#! /usr/bin/env python3

n = int(input())
w = [input() for _ in range(n)]

words = set()

res = True
char = ''

for word in w:
    if word in words:
        res = False
        break
    if char != '' and word[:1] != char:
        res = False
        break
    words.add(word)
    char = word[-1:]


if res == True:
    print("Yes")
else:
    print("No")


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

#define  range(i, l, r) for (int i = (int)(l); i < (int)(r); ++(i))
#define rrange(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); --(i))

#define  whole(f, x, ...) ([&](decltype((x)) container) { return (f)(  begin(container),  end(container), ## __VA_ARGS__); })(x)
#define rwhole(f, x, ...) ([&](decltype((x)) container) { return (f)( rbegin(container), rend(container), ## __VA_ARGS__); })(x)

#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

using int32 = int;
using int64 = long long;

const int   mod   = 1e9 + 7;
const int32 inf   = 1001001001;
const int64 infll = 1001001001001001001ll;

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

struct IoSetup { IoSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup;

template <typename T = int64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } 
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << p.first << " " << p.second; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }

template <typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

class union_find {
private:
  std::vector< int > data_;

public:
  union_find(std::size_t size) : data_(size, -1) {}

  std::size_t size() const {
    return data_.size();
  }

  // x を含む集合の representative を経路圧縮しながら返す
  int get_root(int x) {
    return (data_[x] < 0 ? x : data_[x] = get_root(data_[x]));
  }

  // x が集合の representative なら true を返す
  bool is_root(int x) {
    return x == get_root(x);
  }

  // x と y が同じ集合に含まれるなら true を返す
  bool same(int x, int y) {
    return get_root(x) == get_root(y);
  }

  // x を含む集合と y を含む集合を併合
  void unite(int x, int y) {
    x = get_root(x); y = get_root(y);
    if (x == y) return;
    
    if (data_[x] > data_[y]) std::swap(x, y);
    data_[x] += data_[y];
    data_[y] = x;
  }

  // x を含む集合の要素数を返す
  int element_count(int x) {
    return -data_[get_root(x)];
  }
};

void solver() {
  int N = input(), M = input();
  union_find uf(N);
  range(i, 0, M) {
    int x = input() - 1, y = input() - 1, z = input();
    uf.unite(x, y);
  }

  int ans = 0;
  range(i, 0, N) {
    if (uf.is_root(i)) ans++;
  }

  cout << ans << endl;
}

signed main(int argc, char *argv[]) {
  solver();
}

Measured memory_bytes: 640
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//Abdulhamid Han
//Bismillahirrahmanirrahim
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█▄█
//█─█─█▄─█▄─█─█─█─█
 

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t,vis[105];
int cev;
string s;
vector<int> v;

int main(void){
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++)vis[i*j]=1;
	}
	scanf("%d",&n);
	if(vis[n]==1){printf("Yes\n");}
	else printf("No\n");
	return 0;
}


Measured memory_bytes: 256
// D - XOR World
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll f0(ll n){//f(0,n)
	ll c = 0;
	for(int bit=0; (n>>bit)>0; ++bit){
		ll T = 1LL<<(bit + 1);//cycle
		ll H = T>>1LL;//half cycle
		ll a = (n/T) * H;
		ll b = (n/H)&1? (n%H) + 1LL: 0LL;
		if((a+b)&1LL) c |= 1LL<<bit;//odd -> bit on
	}
	return c;
}

ll f(ll A, ll B){
	return f0(B) ^ f0(A-1);
}

int main(){
	ll A,B; cin>>A>>B;
	cout<<  f(A,B) <<endl;
}

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

//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3", "Ofast", "unroll-loops", "fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")


#define int long long
#define endl '\n'

using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int i, j, n, m;
    cin >> n >> m;
    cout << n * (n - 1) / 2 + m * (m - 1) / 2 << endl;
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

using namespace std;

typedef long long ll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vec) {
    os << "{";
    REP(i, vec.size()) {
        os << vec[i] << " ";
    }
    os << "}";

    return os;
}

ll pow_mod(ll a, ll p) {
    ll res = 1;
    while(p) {
        if (p & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        p >>= 1;
    }

    return res;
}


ll mod_inv(ll a, ll m) {
    ll b = m, u = 0, v = 1;
    while(a) {
        ll t = b / a;
        swap(b -= t * a, a);
        swap(u -= t * v, v);
    }

    return (u % m + m) % m;
}

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

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}


map<ll, int> get_primes(ll m, ll M) {
    map<ll, int> p;
    p[1] = 1;
    int s[m];
    REP(i, m) s[i] = i;
    for(int i = 2; i <= m; ++i) {
        if (s[i] != i) continue;

        for(int j=i+i; j <= m; j += i) {
            s[j] = i;
        }

        int cnt = 0;
        while(M % i == 0) {
            M /= i;
            ++cnt;
        }
        if (cnt > 0) p[i] = cnt;
    }
    if (M != 1) p[M] = 1;

    return p;
}


#ifdef LOCAL
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...)
#endif


int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int N; ll M;
    cin >> N >> M;

    int m = int(floor(sqrt(M))) + 1;
    map<ll, int> p = get_primes(m, M);

    int n = N + 1;
    bool c[n][2];
    REP(i, n) {
        c[i][0] = false;
        c[i][1] = false;
    }
    c[1][0] = true;

    ll mm = inf;
    int b = 0;
//    for (auto it = p.begin(); it != p.end(); ++it) debug(it->fi, it->se)
    for (auto it = p.begin(); it != p.end(); ++it) {
        REP(i, it->se) {
            REP(i, n) {
                if (c[i][b]) {
                    ll t = i * it->fi;
                    if(t < N) {
                        c[i][b^1] = true;
                        c[t][b^1] = true;
                    } else {
//                        debug(t)
                        mm = min(mm, t);
                    }
                }
            }
            b ^= 1;
        }
    }
    
    cout << fixed << setprecision(20);
    cout << int(M / mm) << endl;

}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <sys/types.h>
#include <unistd.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

const pid_t pid = getpid();
// Problem Specific Parameter:

bool visited[3010][3010];
ll dp[3010][3010];
ll a[3010];
const ll inf = 1LL << 50;

ll rec(ll l, ll r, bool first){
	if(l == r) return 0LL;
	if(visited[l][r]) return dp[l][r];
		
	visited[l][r] = true;
	const ll head = a[l] -rec(l + 1, r , first^1);
	const ll tail = a[r - 1] -rec(l, r - 1 , first^1);
	dp[l][r] = max(head, tail);
	return dp[l][r];
}

int main(void){
	int n;
	cin >> n;
	rep(i,n) cin >> a[i];
	cout << rec(0,n,true) << endl;
	return 0;
}

Measured memory_bytes: 80000
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		if(A <= 5)
			System.out.println(0);
		else if(A<=12)
			System.out.println(B/2);
		else
			System.out.println(B);

	}

}


Measured memory_bytes: 22228
#include <iostream>
using namespace std;
int main() {
	int price = 700;
	char a[3];
	cin >> a[0] >> a[1] >> a[2];
	for (int i = 0; i < 3; i++)
		price += (a[i] == 'o') * 100;
	cout << price;
	return 0;
}

Measured memory_bytes: 256
using System;
class AS
{
static void Main()
{
string st= Console.ReadLine();
int []a=new int[26];
string m="";
for(int i=0;i<st.Length;i++)
{
     m=st.Substring(i,1);
if(m=="q"){a[1]++;}
else if(m=="w"){a[0]++;}
else if(m=="e"){a[2]++;}
else if(m=="r"){a[3]++;}
else if(m=="t"){a[4]++;}
else if(m=="y"){a[5]++;}
else if(m=="u"){a[6]++;}
else if(m=="i"){a[7]++;}
else if(m=="o"){a[8]++;}
else if(m=="p"){a[25]++;}
else if(m=="a"){a[9]++;}
else if(m=="s"){a[10]++;}
else if(m=="d"){a[11]++;}
else if(m=="f"){a[12]++;}
else if(m=="g"){a[13]++;}
else if(m=="h"){a[14]++;}
else if(m=="j"){a[15]++;}
else if(m=="k"){a[16]++;}
else if(m=="l"){a[17]++;}
else if(m=="z"){a[18]++;}
else if(m=="x"){a[19]++;}
else if(m=="c"){a[20]++;}
else if(m=="v"){a[21]++;}
else if(m=="b"){a[22]++;}
else if(m=="n"){a[23]++;}
else if(m=="m"){a[24]++;}

}
int ans=0;
for(int i=0;i<26;i++){
if(a[i]%2==0){ans++;}
} if(ans==26){Console.WriteLine("Yes");
}else {Console.WriteLine("No");}
}
}

Measured memory_bytes: 11092
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair <int, int> pr;
map <int, int> mp;
set <int> sst;
vector <int> vect;
priority_queue <pr> qua;
int n;

int main() {
	cin >> n;
	if(n & 1) cout << n * 2 << endl;
	else cout << n << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rep_ll(i,n) for(ll i = 0; i < (ll)(n); i++)
using namespace std;
typedef long long ll;
typedef unsigned long long u_ll;
typedef pair<int, int> pair_;
const long double PI = (acos(-1));
const int INF = 1001001001;
const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, -1, 0, 1};
ll mod = 1000000007;
int main(){
    int n;
    cin >> n;
    vector<u_ll> a(n);
    rep(i,n) cin >> a[i];
    u_ll res = 1;
    int res_1 = 1;
    rep(i, n){
        if(a[i]==0) res_1=2;
    }
    if(res_1==1){
    rep(i,n){
        int keta_res = log10(res)+1;
        int keta_a = log10(a[i])+1;
        res*=a[i];
        if((keta_res+keta_a>19)&&(res!=1000000000000000000)){
            res_1 = 0;
            break;
        }
        if(res>1000000000000000000) {
            res_1 = 0;
            break;
        }
    }
    }

    if(res_1==1) cout << res;
    else if( res_1 == 0) cout << -1;
    else cout << 0;

}

Measured memory_bytes: 4048
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define INF 1000000000 //1e9
#define int long long

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

    int N, K;
    cin>>N>>K;

    if (K == 0) {
        cout << N * N << endl;
        return 0;
    }

    ll ans = 0;
    FOR(b, 1, N+1) {
        int p = N / b;
        int r = N % b;
        ans += max(0LL, (b - K) * p);
        ans += max(0LL, r - K + 1);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define deb(x) cout << #x << "=" << x << endl;
const int N = 3e3+7;
string s,t; int n,m;
int dp[N][N];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> s >> t; n = s.size(); m = t.size();
    for (int i = 1; i <= n; i++) {
        dp[i][0]=0; dp[0][i]=0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i-1]==t[j-1]) {
                dp[i][j]=dp[i-1][j-1]+1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    // cout << dp[n][m] << endl;
    int tot = dp[n][m];
    vector<int> vals(tot);
    int i = n, j =m;
    
    while (j>0||i>0) {
        if (i>0&&j>0 && s[i-1]==t[j-1]) {
            vals[--tot]=s[i-1];
            i--; j--;
        } else if (i==0 || (j>0 && dp[i][j-1] > dp[i-1][j])) {
            j--;
        } else {
            i--;
        }
    }
    for (char c : vals) cout << c;
    if (vals.size() > 0) cout << endl;

    return 0;
}


Measured memory_bytes: 38888
// -*- coding:utf-8-unix -*-

use proconio::{fastout, input};
use std::collections::BTreeMap;

#[fastout]
fn main() {
    input! {
        n: usize,
        s_str: [String; n],
    }
    let mut s: Vec<String> = Vec::new();
    for si in s_str {
        s.push(si.chars().rev().collect());
    }
    s.sort_unstable_by_key(|x| x.len());
    let mut ans: u64 = 0;
    let mut already_seen: BTreeMap<&str, Vec<bool>> = BTreeMap::new();
    for i in 1..=n {
        let nowstr = s[i - 1].as_str();
        let nownagasa = nowstr.len();
        let nowbytes = nowstr.as_bytes();
        let mut have_in_prefix: Vec<bool> = vec![false; 26];
        let saishono = nowbytes[nownagasa - 1] - b'a';
        have_in_prefix[saishono as usize] = true;
        for j in 1..nownagasa {
            have_in_prefix[(nowbytes[nownagasa - 1 - j] - b'a') as usize] = true;
            if let Some(atable) = already_seen.get(&nowstr[0..nownagasa - 1 - j]) {
                for k in 0..26 {
                    if !have_in_prefix[k as usize] {
                        continue;
                    }
                    if atable[k] {
                        ans += 1;
                    }
                }
            }
        }
        let nowstr2 = s[i - 1].as_str();
        let thetable = already_seen
            .entry(&nowstr2[0..nowstr2.len() - 1])
            .or_insert(vec![false; 26]);
        thetable[saishono as usize] = true;
    }
    println!("{}", ans);
}


Measured memory_bytes: 29348
MOD = 10 ** 9 + 7

def sieve(n):
    srn = int(n ** 0.5) + 1
    f = [False] * (srn + 1)
    res = []
    for i in range(2, srn + 1):
        if f[i]:
            continue
        res.append(i)
        for j in range(2 * i, srn + 1, i):
            f[j] = True
    return res

def trial_division(n):
    res = dict()
    for i in range(2, n+1):
        m = i
        for p in pn:
            while m % p == 0:
                res[p] = res.get(p, 0) + 1
                m //= p
            if m == 1:
                break
        if m > 1:
            res[m] = res.get(m, 0) + 1
    return res

N = int(input())
pn = sieve(N)
fn = trial_division(N)
res = 1
for f in fn.values():
    res *= (f + 1)
    res %= MOD
print(res)

Measured memory_bytes: 9344
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
	int n;
	int a[1010]={};
	cin>>n;
	FOR(i,0,n){
		cin>>a[i];
	}
	int mn=mod;
	FOR(t,-100,101){
		int s=0;
		FOR(i,0,n){
			s+=(a[i]-t)*(a[i]-t);
		}
		mn=min(mn,s);
	}
	cout<<mn<<endl;
    return 0;
}


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

int main() {
    int n, m, x;
    cin >> n >> m >> x;
    map<int, int> a;
    for(int i=0; i<m; i++){
        int aa;
        cin >> aa;
        aa--;
        a[aa]++;
    }
    int ans_a = 0;
    int ans_b = 0;
    for(int i=x-1; i<n; i++){
        ans_a += a[i];
    }

    for(int i=x-1; i>=0; i--){
        ans_b += a[i];
    }

    cout << min(ans_a, ans_b) << endl;

    return 0;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/abc171/tasks/abc171_d
#include<bits/stdc++.h>
using namespace std;

int main(int argc, char* argv[]) {
	int n;
	cin >> n;
	map<int, int> m;
	long long sum = 0;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		sum += tmp;
		++m[tmp];
	}
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int b, c;
		cin >> b >> c;
		if (m.count(b)) {
			sum = sum + (c-b)*m[b];
			m[c] = m[c]+m[b];
			m.erase(b);
		}
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 6488
MOD = 998244353

def solve(A,B,C,D):
    H,W = C-A, D-B
    dp = [[0]*(W+1) for _ in range(H+1)]

    t = 1
    for i in range(W+1):
        dp[0][i] = t
        t *= A
        t %= MOD

    for j in range(1,H+1):
        dp[j][0] = (dp[j-1][0]*B)%MOD

        for i in range(1,W+1):
            dp[j][i] = dp[j-1][i]*(B+i) + dp[j][i-1]*(A+j) - dp[j-1][i-1]*(B+i-1)*(A+j-1)
            dp[j][i] %= MOD

    return dp[-1][-1]


if __name__ == '__main__':
    print(solve(*map(int,input().split())))

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

int a[100005];

int main()
{
    int n;
    scanf("%d",&n);
    for (int i = 0; i < n; i++) scanf("%d",&a[i]);
    sort(a, a + n);

    if (a[0] == a[n - 1])
    {
        if (a[0] == n - 1 || a[0] <= n / 2)
        {
            printf("Yes\n");
        }
        else printf("No\n");
    }
    else if (a[0] + 1 == a[n - 1])
    {
        int lo = upper_bound(a, a + n, a[0]) - a;
        int hi = n - lo;

        // lo만큼은 하나씩만 있고,
        // hi만큼은 2개 이상씩 있다

        if (lo > a[0]) printf("No\n");
        else
        {
            int rem = a[n - 1] - lo;
            if (rem <= hi / 2)
            {
                printf("Yes\n");
            }
            else printf("No\n");
        }
    }
    else
    {
        printf("No\n");
    }
}


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

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie();cout.tie();

  int n, m;
  cin >> n >> m;

  string s; cin >> s;
  reverse(s.begin(), s.end());

  int pos = 0;
  int caiu = 0;
  bool possivel = true;
  vector<int> pulos;
  for(int i = 1; i <= n; i++){
    if(i-pos > m){
      if(caiu == pos){
        possivel = false;
        break;
      }
      pulos.push_back(caiu - pos);
      pos = caiu;
    }
    if(s[i] == '0' && i - pos <= m){
      caiu = i;
    }
  }
  if(possivel){
    pulos.push_back(n - pos);
  }

  if(!possivel) cout << "-1" << endl;
  else{
    for(int i = (int)pulos.size() - 1; i >= 0; i--){
      cout << pulos[i];
      if(i !=0) cout << " ";
    }
    cout << endl;
  }

}


Measured memory_bytes: 1096
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = (ll)a;i < (ll)b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = (ll)b-1LL;i >= (ll)a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<ld,ld> pdd;

const ll INF=(1LL<<50);
#if __cplusplus<201700L
ll gcd(ll a, ll b) {
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif
template<class T>
bool chmax(T& a,const T& b){
  if(a<b){
    a=b;
    return true;
  }
  return false;
}
template<class T>
bool chmin(T& a,const T& b){
  if(a>b){
    a=b;
    return true;
  }
  return false;
}
template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}



int main(){
  cout<<setprecision(1000);
  ll H,W,K;
  cin>>H>>W>>K;
  vector<string> S(H);
  REP(H){
    cin>>S[i];
  }
  ll ans=H-1+W-1;
  REP(1LL<<(H-1)){
    ll cutH=__builtin_popcountll(i);
    vector<ll> cnt(cutH+1);
    ll cut=cutH;
    For(j,W){
      ll cur=0;
      vector<ll> zouka(cutH+1);
      For(k,H){
        if(S[k][j]=='1'){
          ++zouka[cur];
        }
        if((i&(1LL<<k))){
          ++cur;
        }
      }
      bool f=false;
      For(k,zouka.size()){
        if(zouka[k]>K){
          goto END_LOOP;
        }
        if(zouka[k]+cnt[k]>K){
          ++cut;
          f=true;
          break;
        }
      }
      if(f){
        fill(cnt.begin(),cnt.end(),0);
      }
      For(k,zouka.size()){
        cnt[k]+=zouka[k];
      }
    }
    ans=min(ans,cut);
END_LOOP:;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
// import java.io.*;

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

        int num = sc.nextInt();

        ArrayList<Integer> array = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            int tmp = sc.nextInt();
            array.add(tmp);
        }

        TreeSet<Integer> tmp = new TreeSet<>();

        for (int i = 0; i < num; i++) {
            tmp.add(array.get(i));
        }

        while (!tmp.isEmpty()) {
            sb.append(tmp.pollFirst());
            if (!tmp.isEmpty()) sb.append(' ');
        }

        /* for (int i = 0; i < array.size(); i++) {
            sb.append(array.get(i));
            if (i != array.size() - 1) sb.append(' ');
        } */

        System.out.println(sb);
        
        sc.close();
    }
}



Measured memory_bytes: 71756
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <map>

#define ll long long
#define REP(i,n) for(int i = 0; i < n; i++)
#define PI 3.141592653589

using namespace std;

void solve_C_re(){
    int n;
    cin >> n;

    map<string, int> mp;
    REP(i,n){
        string p;
        cin >> p;
        mp[p]++;
    }

    int max = 0;
    for(const auto &x : mp){
        int v = x.second;
        if(v > max) max = v;
    }

    for(auto i = mp.begin(); i != mp.end(); i++){
        if(i -> second == max){
            cout << i -> first << endl;
        }
    }
}

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

Measured memory_bytes: 25216
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;

int main(){
    long long n;
    cin >> n;
    set<long long> T;

    long long a;

    for(long long i = 0; i < n; i++){
        cin >> a;
        if(T.find(a) == T.end()){
            T.insert(a);
        }
        else{
            T.erase(a);
        }
    }

    printf("%lld\n", (long long)T.size());

    return 0;
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, start, end) for(int i = start; i < end; i++)
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << (x) << endl;
#define MAX 999999999

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

typedef long long ll;

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

    int n;
    string a, b, c;
    cin >> n >>  a >> b >> c;

    int cnt = 0;
    rep(i, n){
        set<char> tmp;
        tmp.insert(a[i]);
        tmp.insert(b[i]);
        tmp.insert(c[i]);
        cnt += tmp.size() - 1;
    }

    cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
using namespace std;

string d[10] = {"",
                "\',.!?",
                "abcABC",
                "defDEF",
                "ghiGHI",
                "jklJKL",
                "mnoMNO",
                "pqrsPQRS",
                "tuvTUV",
                "wxyzWXYZ"};

signed main(){
    string s;
    while(cin >> s){
        string ans = "";
        int now = s[0] - '0';
        int cnt = 1;
        s += "A";
        rep(i, 1, s.size()){
            if(s[i] == now + '0'){
                cnt++;
            }else{
                if(now == 0){
                    rep(j, 0, cnt - 1) ans += " ";
                }else{
                    ans += d[now][(cnt - 1) % (int)(d[now].size())];
                }
                now = s[i] - '0';
                cnt = 1;
            }
            if(s[i] == 'A') break;
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 1196
#include<stdio.h>
#define MAX 100

int min(int x, int y);

int main(){
  int i, j, k, w, n, p[MAX+1], m[MAX+1][MAX+1];
  
  scanf("%d", &n);
  for ( i = 1; i <= n; i++ ){
    scanf("%d%d", &p[i-1], &p[i]);
  }

  for ( i = 1; i <= n; i++ ){
    m[i][i] = 0;
  }
  for (w=2;w<= n;w++ ){
    for ( i = 1; i <= n-w+1; i++ ){
      j = i+w-1;
      m[i][j]=100000000;/*INFINITY*/
      for ( k = i; k <= j-1; k++ ){
	m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]);
      }
    }
  }

  printf("%d\n", m[1][n]);
  
  return 0;
}
int min(int x, int y){
  return x < y ? x : y;
}



Measured memory_bytes: 2052