akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#define SET_SIZE 26
#define MAX 256

#define show {int i=0;while(sentence[i]!='\n')printf("%c",sentence[i++]);printf("\n");}

int gcd(int x, int y){
	int r;
	while((r=x%y)!=0) x=y, y=r;
	return y;
}

int nextA(int a){
	while(gcd(++a,SET_SIZE)!=1);
	return a;
}

int main(void){
	int n, state, i, a, b; char sentence[MAX];
	
	scanf("%d%*c",&n);
	
	for(;n--;){
		a=1, b=-1;
	
		/* load */
		i=0; while((sentence[i++]=getchar())!='\n');
		
		/* check */
		while(1){
			state=1, i=-1;
			
			while(1){
				if(sentence[++i]=='\n') break;
				else if(sentence[i]==' ' && state==4) break;
				else if(sentence[i]==' ') state=1;
				else if(sentence[i]=='t' && state==1) state=2;
				else if(sentence[i]=='h' && state==2) state=3;
				else if(sentence[i]=='i' && state==3) state=5;
				else if(sentence[i]=='a' && state==3) state=6;
				else if(sentence[i]=='s' && state==5) state=4;
				else if(sentence[i]=='t' && state==6) state=4;
				else state=0;
			}
			
			if(state==4) break;
			
			/* next */
			else {
				b++;
				if(b==SET_SIZE) a=nextA(a), b=0;
				
				for(i=0; sentence[i]!='\n'; i++)
				if('a'<=sentence[i] && sentence[i]<='z')
					sentence[i]=((sentence[i]-'a')*a+b)%26+'a';
			}
		}
		
		i=0; while(sentence[i]!='\n') printf("%c",sentence[i++]);
		printf("\n");
	}
}

Measured memory_bytes: 0
from sys import stdin
n = int(stdin.readline())

roomlist = [[[0]*10 for i in range (0,3)] for k in range (0,4)]

for _ in range(n):
    b, f, r, v  = map(int, stdin.readline().split())
    roomlist[b-1][f-1][r-1] += v

for buildingnum in range(4):
    for floornum in range(3):
        print('',*roomlist[buildingnum][floornum])
    if buildingnum != 3:
        print('#'*20)


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

void solve()
{
	ll n;
	cin>>n;
	ll freq1[n+1] = {},freq2[n+1] = {};
	ll a[n],b[n];
	ll f1 = -1, f2 = -3;
	for (int i = 0; i < n; ++i)
	{
		// ll k;
		cin>>a[i];
		freq1[a[i]]++;
		if(freq1[a[i]]*2>n)
			f1 = a[i];
	}
	for (int i = 0; i < n; ++i)
	{
		// ll k;
		cin>>b[i];
		freq2[b[i]]++;
		if(freq2[b[i]]*2>n)
			f2 = b[i];
	}
	if(f1==f2)
	{
		// cout<<f1<<f2<<endl;
		cout<<"No"<<endl;
		return;
	}
	sort(b,b+n,greater<ll>());
	ll k = 0;
	for (int i = 1; i < n; ++i)
	{
		if(a[i]==b[i])
		{
			ll prev = k;
			while(a[k]==b[i]||a[i]==b[k])
			{
				k++;
				k %= n;
				if(k==prev)
				{
					cout<<"No"<<endl;
					return;
				}
			}
			swap(b[k],b[i]);
			k++;
			k %= n;
		}
	}
	for (int i = 0; i < n; ++i)
	{
		if(a[i]==b[i])
		{
			cout<<"No"<<endl;
			return;
		}
	}
	cout<<"Yes"<<endl;
	for (int i = 0; i < n; ++i)
	{
		cout<<b[i]<<" ";
	}
	cout<<endl;
}

int main()
{
	ll t = 1;
	// cin>>t;
	while(t--)
	{
		solve();
	}
}

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

int main() {
  int a, b;
  cin >> a >> b;
  bool possible = false;
  if(a % 3 == 0 || b % 3 == 0 || (a+b) % 3 == 0) {
    possible = true;
  }
  if(possible) {
    cout << "Possible" << endl;
  } else {
    cout << "Impossible" << endl;
  }
}

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

int main() {
  int n; cin >>n;
  vector<int> p(n), q(n);
  for (int i=0; i<n; i++){
    cin >>p.at(i); q.at(i) = p.at(i);
  }
  sort(q.begin(), q.end());
  string ans = "YES";
  int cnt = 0;
  for (int i=0; i<n; i++){
    if (p.at(i) != q.at(i)) cnt++;
  }
  if (cnt>2) ans = "NO";
  
  cout <<ans;
  cout <<endl;
}


Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Text;

namespace AtTest.C_Challenge
{
    class ABC_076
    {
        static void Main(string[] args)
        {
            Method(args);
            Console.ReadLine();
        }

        static void Method(string[] args)
        {
            char[] s = Console.ReadLine().ToCharArray();
            char[] t = Console.ReadLine().ToCharArray();
            for (int i = s.Length - t.Length; i >= 0; i--)
            {
                bool ok = true;
                for(int j = 0; j < t.Length; j++)
                {
                    if (s[i + j] == t[j] || s[i + j] == '?')
                    {
                        continue;
                    }
                    else
                    {
                        ok = false;
                        break;
                    }
                }
                if (ok)
                {
                    for(int j = 0; j < t.Length; j++)
                    {
                        s[i + j] = t[j];
                    }
                    string result = new string(s).Replace('?', 'a');
                    Console.WriteLine(result);
                    return;
                }
                else
                {
                    continue;
                }
            }
            Console.WriteLine("UNRESTORABLE");
        }

        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;

    string s[n];
    cin >> s[0];
    bool f = true;
    for (int i = 1; i < n; i++) {
        cin >> s[i];
        for (int j = 0; j < i; j++) {
            if (s[i] == s[j]) {
                f = false;
                break;
            }
        }
        if (s[i][0] != s[i-1][s[i-1].length()-1]) {
            f = false;
            break;
        }
    }

    cout << (f ? "Yes" : "No") << endl;

    return 0;
}

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

#define                           int                         long long
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<int,int>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);




using namespace std;

const int inf=1e18;
const int mod=1e9+7;
const int M=100009;

inline int bigmod(int B,int P){int R=1;while(P>0){if(P&1){R=(R*B)%mod;}P>>=1;B=(B*B)%mod;}return R;}
inline int ad(int x,int y){int ret=(x%mod+y%mod)%mod;if(ret<0){ret+=mod,ret=ret%mod;}return ret;}
inline int sub(int x,int y){int ret=((x%mod)-(y%mod)+mod)%mod;if(ret<0){ret+=mod,ret=ret%mod;}return ret;}
inline int gun(int x,int y){int ret=((x%mod)*(y%mod))%mod;if(ret<0){ret+=mod,ret=ret%mod;}return ret;}


 main()

{
    fast
    string s;
    cin>>s;
    int sz=s.size();
    int cnt[27];clr(cnt);
    int dp[sz+3];
    dp[0]=1;
    cnt[s[0]-'a']++;
    for(int i=1;i<sz;i++)
    {
        dp[i]=dp[i-1];
        int onno=i-cnt[s[i]-'a'];
        dp[i]+=onno;
        cnt[s[i]-'a']++;
    }
    cout<<dp[sz-1]<<endl;
    return 0;

}





































Measured memory_bytes: 2196
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <iomanip>
#include <cmath>
#include <queue>
#include <bitset>
#include <numeric>
#include <array>
#include <cstring>
#include <random>
#include <chrono>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int main() {

  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  int n = 0;

  cin >> n;

  vector<ll> a(n);

  vector<ll> dp(n + 1);

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

  dp[0] = 1000;

  for(int i = 0; i < n; i++) {
    ll cur = dp[i] / a[i], left = dp[i] % a[i];
    for(int j = i + 1; j < n; j++) {
      dp[j] = max(dp[i], max(dp[j], cur * a[j] + left));
    }
  }

  cout << dp[n - 1];

  return 0;
}
/*

*/


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

// https://atcoder.jp/contests/abc123/tasks/abc123_c

using namespace std;

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

  long long int m = numeric_limits<long long int>::max();
  for (int i = 0; i < 5; i++) {
    m = min(a[i], m);
  }

  long long int p;
  if (n % m == 0) {
    p = n / m;
  } else {
    p = n / m + 1;
  }
  cout << p + 4 << endl;
  return 0;
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <iomanip>
#include <string>
#include <math.h>
#include<set>
#include<stdio.h>
#include <bitset>
#define ii int64_t
#define PI 3.14
#define lli long long int
#define li long int
#define mod 1000000007
#define f(x,n) for(int64_t x=0;x<n;++x)
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// while(scanf("%d",&n)!=EOF)
using namespace std;



int main()
{
    fio
    ii n,i,j,k,x;
    cin>>n>>k;
    ii h[n+3],dp[n+3];
    for(i=1;i<=n;++i)cin>>h[i];
    dp[2]=abs(h[2]-h[1]);dp[1]=0;
    
    for(i=3;i<=n;i++)
    {
        dp[i]=1e10;
        for(j=i-1;j>0 && i-j<=k;--j)
            dp[i]=min(dp[j]+abs(h[j]-h[i]),dp[i]);
    }
    cout<<dp[n];
    
    



}


Measured memory_bytes: 1792
N=int(input())
S=input()
DP=[0]*N
l=0
for i,x in enumerate(S):
  DP[i]+=l
  if x=="E":
    l+=1
r=0
for i,y in enumerate(S[::-1]):
  DP[N-1-i]+=r
  if y=="W":
    r+=1
print(N-1-max(DP))

Measured memory_bytes: 15436
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
  }
  int a = 0, b = 0, c = 0;
  for (int i = 0; i < N; i++){
    if (A[i] % 4 == 0){
      a++;
    } else if (A[i] % 2 == 0){
      b++;
    } else {
      c++;
    }
  }
  if (b == 0){
    if (c <= a + 1){
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  } else {
    if (c <= a){
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

#define PB push_back
#define MP make_pair

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

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

int main() {
  ll N, M, ans;
  cin >> N >> M;
  if (N==1 || M==1) {
    if (N != 1) {
      ans = N - 2;
    } else if (M != 1) {
      ans = M - 2;
    } else {
      ans = 1;
    }
  } else {
    ans = (N - 2) * (M - 2);
  }

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


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

//#define int long long
//using ll = boost::multiprecision::cpp_int;
using ll = long long;
//constexpr int INF = 1e9;//INT_MAX=(1<<31)-1=2147483647
constexpr ll INF = (ll)1e18;//(1LL<<63)-1=9223372036854775807
constexpr ll MOD = (ll)1e9 + 7;
constexpr double EPS = 1e-9;
constexpr int dx[4]={1,0,-1,0};
constexpr int dy[4]={0,1,0,-1};
#ifdef LOCAL_ENV
	#define debug(var) std::cout<<#var" = "<<var<<std::endl
#else
	#define debug(var)
#endif
#define p(var) std::cout<<var<<std::endl
#define rep(i, n)   for(ll i=0, i##_length=(n); i< i##_length; ++i)
#define repeq(i, n) for(ll i=1, i##_length=(n); i<=i##_length; ++i)
#define all(a) (a).begin(), (a).end()
#define PI (acos(-1))
template<typename T> inline T power(T x, T n){ return n ? power(x*x%MOD,n/2)*(n%2?x:1)%MOD : 1; }
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b,a%b) : a; }
template<typename T> inline T lcm(T a, T b) { return a / gcd(a,  b) * b; }
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); }
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
	for (int i = 0, len = v.size(); i < len; ++i){
		s << v[i]; if (i < len - 1) s << "\t";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
	for (int i = 0, len = vv.size(); i < len; ++i){
		s << vv[i] << endl;
	}
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const map<T1, T2>& m) {
	s << "{" << endl;
	for (typeof(m.begin()) itr = m.begin(); itr != m.end(); ++itr){
		s << "\t" << (*itr).first << " : " << (*itr).second << endl;
	}
	s << "}" << endl;
	return s;
}

/*-----8<-----8<-----*/

class UnionFind {
public:
	vector<ll> v;
	vector<ll> diff_weight;
	UnionFind(size_t size) : v(size, -1), diff_weight(size, 0) {}

	ll root(ll x) {
		if (v[x] < 0) {
			return x;
		} else {
			ll r = root(v[x]);
			diff_weight[x] += diff_weight[v[x]];
			return v[x] = r;
		}
	}

	bool is_root(ll x) {
		return x == root(x);
	}

	bool is_same(ll x, ll y) {
		return root(x) == root(y);
	}

	ll weight(ll x) {
		root(x);
		return diff_weight[x];
	}

	//weight(y) = weight(x) + w / xが親
	bool unite(ll x, ll y, ll w = 0) {
		w += weight(x) - weight(y);
		x = root(x);
		y = root(y);
		if (x == y) return false;
		if (v[x] > v[y]) {
			swap(x, y);
			w *= -1;
		}
		v[x] += v[y];
		v[y] = x;
		diff_weight[y] = w;
		return true;
	}

	ll size(ll x) {
		return -v[root(x)];
	}

	ll diff(ll x, ll y) {
		return weight(y) - weight(x);
	}
};


////


signed main() {
	ll N, M;
	cin >> N >> M;

	UnionFind t(N);

	rep(i, M) {
		ll l,r,d;
		cin>>l>>r>>d;
		l--;r--;
		if(t.is_same(l,r)){
			ll dif=t.diff(l,r);
			if(d!=dif){
				debug(i);
				debug(d);
				debug(dif);
				p("No");
				return 0;
			}
		}else{
			t.unite(l,r,d);
		}
	}
	p("Yes");
	return 0;
}




Measured memory_bytes: 1792
from heapq import heappush, heappop

def main():
    INF = float("inf")

    N, M, *LRC = map(int, open(0).read().split())

    E = [[] for _ in range(N)]
    for i in range(N - 1):
        E[i + 1].append((i, 0))
    for l, r, c in zip(*[iter(LRC)] * 3):
        E[l - 1].append((r - 1, c))

    D = [INF] * N
    D[0] = 0

    Q = [0]
    while Q:
        t = heappop(Q)
        dist, cur = t // N, t % N
        for nxt, cost in E[cur]:
            cand = dist + cost
            if D[nxt] > cand:
                D[nxt] = cand
                heappush(Q, cand * N + nxt)

    print(-1 if D[N - 1] == INF else D[N - 1])

main()


Measured memory_bytes: 50292
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
	#ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    string s;
    cin>>s;
    cout<<((s[0]==s[2])?"Yes":"No");
    return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
int main(){
    ll a,b,n;
    cin >> a >> b >> n;
    if(b<=n){
        cout<<(b-1)*a/b<<endl;
    }else{
        
        cout << n*a/b<<endl;
    }
  return 0;
}

Measured memory_bytes: 3604
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
using ll = long long int;
using namespace std;
double pi = 3.141592653589793238;

#define FOR(i,N) for(int i=0;i<N;i++)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)



int main() {
	int n;
	cin >> n;

	int num[21];
	unordered_map<int, bool> m;
	FOR(i, n) {
		cin >> num[i];
	}

	FOR(i, 2 << n) {
		int a = 0;
		FOR(j, n) {
			if (i & 2 << j) { a += num[j]; }
		}
		m[a] = true;
	}

	int q;
	cin >> q;
	FOR(i, q) {
		int x;
		cin >> x;
		if (m[x]) { cout << "yes\n"; }
		else { cout << "no\n"; }
	}

	return 0;
}


Measured memory_bytes: 3116
# ABC125B - Resale
def main():
    n = int(input())
    V, C = tuple(tuple(map(int, input().rstrip().split())) for _ in range(2))
    ans = sum(i - j for i, j in zip(V, C) if i - j > 0)
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
#include <stdio.h>

int main(void)
{
	int l;
	int a;
	int b;
	int c;
	int d;
	int i;
	int sum_a;
	int sum_b;
	
	for (i = 0; i < 5; i++){
		switch (i){
		  case 0:
		    scanf("%d", &l);
			break;
			
		  case 1:
		    scanf("%d", &a);
			break;
			
		  case 2:
		    scanf("%d", &b);
			break;
			
		  case 3:
		    scanf("%d", &c);
			break;
			
		  case 4:
		    scanf("%d", &d);
			break;
		}
	}
	
	sum_a = a / c;
	sum_b = b / d;
	if (a % c >= 1){
		sum_a++;
	}
	if (b % d >= 1){
		sum_b++;
	}
	if (sum_a >= sum_b){
		printf("%d\n", l - sum_a);
	}
	else if (sum_a <= sum_b){
		printf("%d\n", l - sum_b);
	}
	
	return (0);
}

Measured memory_bytes: 1772
function Main(input) {
  var n = parseInt(input[0]);
  var a = input[1].split(" ");
  var cnt = 0;
  for (var i in a) {
    while(a[i]%2 == 0) {
      a[i] /= 2;
      cnt++;
    }
  }
  console.log(cnt);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8").split("\n"));


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

#define PI 3.1415926535897932
#define MOD 1000000007
#define INF 1e9

#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define ALL(v) (v).begin(), (v).end()
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO  cout << "NO"  << endl
#define No  cout << "No"  << endl

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;


void solve()
{
    int r, D, x; cin >> r >> D >> x;
    REP(i, 10)
    {
        x = r*x-D;
        cout << x << endl;
    }
} 
    
int main() 
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}

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

const long inf = 1e18;
int n, r;
long a[300];
long b[300];
long dp[300][300][300];
long dq[300][300][300];
long dr[300][300][300];

void modify(int i) {
  for (int j = 0; j < n; ++j) {
    long q = inf;
    for (int k = n - 1; k >= 0; --k) {
      q = min(q, dp[i][j][k]);
      dq[i][j][k] = q;
    }

    long r = inf;
    for (int k = 0; k < n; ++k) {
      dr[i][j][k] = r;
      r = min(r, dp[i][j][k] - b[k]);
    }
  }
}

int main() {
  cin >> n >> r;
  if (n == r) {
    cout << 0 << endl;
    return 0;
  }

  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 0; i < n; ++i) b[i] = a[i];
  sort(b, b + n);
  
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= r; ++j) {
      for (int k = 0; k < n; ++k) {
        dp[i][j][k] = inf;
        if (i == 0 && j == (b[k] != a[0])) {
          dp[i][j][k] = b[k];
        }
      }
    }
  }
  
  modify(0);
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j <= r; ++j) {
      for (int k = 0; k < n; ++k) {
        int pj = b[k] == a[i] ? j : j - 1;
        if (pj < 0) continue;
        dp[i][j][k] =
          min(dp[i][j][k], 
            min(dq[i - 1][pj][k], b[k] + dr[i - 1][pj][k])); 
      }
    }
    modify(i);
  }

  long mn = inf;
  for (int j = 0; j <= r; ++j) {
    for (int k = 0; k < n; ++k) {
      mn = min(mn, dp[n - 1][j][k]);
    }
  }
  cout << mn << endl;
}

Measured memory_bytes: 632704
solve :: Char -> String -> Int
solve _ [] = 0
solve curr (s:ss)
  | curr == s = solve next ss
  | otherwise = 1 + solve next ss
    where next = if curr == '0' then '1' else '0'

main :: IO ()
main = do
  s <- getLine
  let a = solve '0' s
  let b = solve '1' s
  print $ min a b

Measured memory_bytes: 7548
fun main(args: Array<String>) {
    val (n,q)=readLine()!!.split(" ").map { it.toInt() }
    val s=readLine()!!
    val lr = Array(q){readLine()!!.split(" ").map { s->s.toInt() }}
    var count =0
    val c = s.mapIndexed{i,c->
        if(c=='A'&&i<s.length-1&&s[i+1]=='C')count+=1
        count
    }
    lr.forEach {
        println(if(it[1]>1)c[it[1]-2]else{0} - if(it[0]>1)c[it[0]-2]else 0)
    }
}

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

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main() {
  int D, G;
  scanf("%d %d", &D, &G);

  vector<P> pc(D);
  for (int i = 0; i < D; ++i) {
    int p, c;
    scanf("%d %d", &p, &c);
    pc[i] = P(p, c);
  }

  int ans = 1e9;
  for (int i = 0; i < 1 << D; ++i) {
    int sum = 0;
    int cnt = 0;
    for (int j = 0; j < D; ++j) {
      if (i >> j & 1) {
	sum += (pc[j].first * (j + 1) * 100) + pc[j].second;
	cnt += pc[j].first;
      }
    }
    bool pass = false;
    if (sum < G) {
      for (int j = D - 1; j >= 0; --j) {
	if (i >> j & 1) continue;
	if (((pc[j].first - 1) * (j + 1) * 100) < G - sum) {
	  pass = true;
	} else {
	  int need = ceil((double)(G - sum) / ((j + 1) * 100)) ;
	  cnt += need;
	}
	break;
      }
    }
    if (!pass) {
      ans = min(ans, cnt);
    }
  }
  printf("%d\n", ans);
  return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0; i < n; i++)
#define repd(i, n) for (int i = n-1; i > -1; i--)
#define repran(i, a,b) for (int i = a; i<b;i++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;
const int MAX_N = 3010;
int dp[MAX_N][MAX_N];
int main()
{
    string s, t;
    cin >> s;
    cin >> t;
    int n = s.size();
    int m = t.size();
    rep(i, n+1) rep(j, m+1)dp[i][j]= 0;
    rep(i, n) rep(j, m){
        if (s[i] == t[j]) {
            dp[i+1][j+1] = dp[i][j]+1;
        } else{
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
        }
    }
    string ans = "";
    while (n > 0 and m > 0){
        if (dp[n][m] == dp[n-1][m]) n--;
        else if (dp[n][m] == dp[n][m-1]) m--;
        else ans += s[n-1], n--, m--;
    }
    reverse(all(ans));
    cout << ans << endl;
}

Measured memory_bytes: 38844
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;

vector<pair<ll,ll>> v[2510];
ll dist[2510];
vector<int> used(2510,0);

void bfs(){
  queue<int> q;
  q.push(0);
  dist[0]=0;
  while(q.size()){
    int x=q.front(); q.pop();
    if(used[x]>3000){ continue; }
    for(auto e:v[x]){
      if(dist[e.F] > dist[x] + e.S){
        dist[e.F] = dist[x] + e.S;
        used[e.F]++;
        q.push(e.F);
      }
    }
  }
}

int main(){
  int n,m,p;
  cin >> n >> m >> p;
  rep(i,m){
    ll a,b,c;
    cin >> a >> b >> c; a--; b--;
    v[a].push_back({b,-c+p});
  }
  rep(i,n){ dist[i]=longinf; }
  
  bfs();
  
  if(used[n-1]>2000){ 
    cout << -1 << endl; 
  } else {
    cout << max(0LL,-dist[n-1]) << endl; 
  }
  return 0;
}


Measured memory_bytes: 3072
// 1_9_A
#include <algorithm>
#include <iostream>
using namespace std;

int main(){
  int count = 0;
  string W, text;
  cin >> W;
  transform(W.begin(), W.end(), W.begin(), ::tolower);
  while(cin >> text){
    if(text == "END_OF_TEXT"){
      cout << count << endl;
      return 0;
    }
    transform(text.begin(), text.end(), text.begin(), ::tolower);
    if(W == text) count++;
  }
}



Measured memory_bytes: 3188
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scan =  new Scanner(System.in);
		
		int n = scan.nextInt();
		int d = scan.nextInt();
		int ans = 0;
		
		for(int i=0;i<n;i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			
			double c = Math.sqrt(Math.pow(a, 2)+Math.pow(b,2));
			if(c<=(double)d){
				ans++;
			}
		}
		
		System.out.println(ans);
		

	}

}


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

static const int N=100;

int main()
{
  int n,p[N+1],m[N+1][N+1];
  cin >> n;
  for(int i=1; i<=n; i++)
    {
      cin>>p[i-1]>>p[i];
    }

  for(int i=1;i<=n;i++)
    {
    m[i][i]=0;
    }
  for(int l=2;l<=n;l++)
    {
      for(int i=1; i<=n-l+1;i++)
	{
	  int j=i+l-1;
	  m[i][j]=(1<<21);
	  for(int 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]);
	    }
	}
    }
  cout<<m[1][n]<<endl;

  return 0;
}




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

typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define ar array
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll mod = 1e9 + 7;
const ll inf = 2e9 + 5;
double PI = 3.14159265358979323846;

template <ll M> struct ModInt {
    int val;
    ModInt(ll x = 0): val((x % M + M) % M) {}
 
    ModInt pow(ll n) const {
        ModInt ans = 1, x = val;
        while (n) {
            if (n & 1) ans *= x;
            x *= x;
            n /= 2;
        }
        return ans;
    }
 
    ModInt inverse() const { return pow(M - 2); }
    ModInt operator+ (const ModInt& m) { return val + m.val < M ? val + m.val : val + m.val - M; }
    ModInt operator- (const ModInt& m) { return val - m.val >= 0 ? val - m.val : val - m.val + M; }
    ModInt operator* (const ModInt& m) { return val * (ll) m.val % M; }
    ModInt operator/ (const ModInt& m) { return *this * m.inverse(); }
    ModInt operator+=(const ModInt& m) { return *this = *this + m; }
    ModInt operator-=(const ModInt& m) { return *this = *this - m; }
    ModInt operator*=(const ModInt& m) { return *this = *this * m; }
    ModInt operator/=(const ModInt& m) { return *this = *this / m; }
 
    friend ostream& operator<<(ostream& os, const ModInt& m) {
        os << m.val;
        return os;
    }

    friend istream& operator>>(istream& is, ModInt& m) {
        is >> m.val;
        return is;
    }
};

using mint = ModInt<(int)1e9 + 7>;

void solve() {

	int n;
	cin >> n;
	if(n < 3){
		cout << 0 << endl;
		return;
	}

	mint ans = 0;
	// vector<vector<mint>> dp(n+1,vector<mint>(n+1));
	vector<mint> dp(n+1,0);
	dp[0]= 1;
	for(int i = 3;i <= n;i++){
		for(int j = 3;j <= i;j++){
			dp[i] += dp[i-j]; 
		}
	}
	cout << dp[n] << endl;

}

int32_t main()
{
    IOS
    // int T; cin >> T; while (T--)
    solve();
    return 0;
}


Measured memory_bytes: 3652
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <list>
#include <numeric>
#include <map>	
#include <cmath>
#include <string>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define Cout(s) cout<<s<<endl
using namespace std;
typedef long long ll;
string Yes(bool b) { if (b) { return "Yes"; } else { return "No"; } }
string YES(bool b) { if (b) { return "YES"; } else { return "NO"; } }
//================================================

bool primejudge(const ll x) {
	if (x == 2)return true;
	if (x < 2 || x % 2 == 0)return false;
	for (int i = 3; i * i <= x; i += 2)
		if (x % i == 0)return false;
	return true;
}

int a = 0, b = 0, c, d, n, k = 0, ans = 0;
string s, t;


int main()
{
	int n, m;
	cin >> n >> m;
	int flag1=0, flag2=n;
	rep(i,m)
	{
		cin >> a >> b;
		flag1 = max(a, flag1);
		flag2 = min(b, flag2);
	}
	if (flag1 > flag2)
		cout << 0 << endl;
	else
		cout << flag2 - flag1 + 1 << endl;

	return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python
"""AtCoder Beginner Contest 169: C - Multiplication 3
https://atcoder.jp/contests/abc169/tasks/abc169_c
"""

from decimal import Decimal


def main():
    inputs = input().split()
    A, B = int(inputs[0]), Decimal(inputs[1])

    print(int(A * B))


if __name__ == '__main__':
    main()


Measured memory_bytes: 9972
# include "bits/stdc++.h"
 
using namespace std;
 
#define endl "\n"
typedef long long int ll;
#define f first
#define s second
 
inline void fastio(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);}
inline void setPrecision(int n){cout.precision(n);}
 
//DEBUG
#define dbg(x) cerr<<(#x)<<": "<<x<<endl
#define dbgV(x) cerr<<(#x)<<": "; for(auto it: x) cerr<<it<<" "; cerr<<endl;
#define dbgS(x) cerr<<(#x)<<": "; for(auto it: x) cerr<<it<<" "; cerr<<endl;
#define dbgM(x) cerr<<(#x)<<": "; for(auto it: x) cerr<<"["<<it.f<<", "<<it.s<<"] "; cerr<<endl;
#define dbg2D(x) cerr<<(#x)<<": \n"; for(auto y: x) { for(auto it: y) cerr<<it<<" "; cerr<<endl; } cerr<<endl;
#define dbgA(x, n) cerr<<(#x)<<": "; for(int i=0;i<n;++i) cerr<<x[i]<<" "; cerr<<endl;
#define dbgVP(x) cerr<<(#x)<<": "; for(auto it: x) cerr<<"["<<it.f<<", "<<it.s<<"] "; cerr<<endl;
 
ll INF = 1e10;
int MOD = 1e9+7;

int main(){
    fastio();

    int n;
    cin >> n;

    int b[n - 1];
    for(int i = 0; i < n - 1; ++i)
    	cin >> b[i];

    int a[n];
    a[n - 1] = b[n - 2];
    int s = b[n - 2];
    for(int i = n - 2; i >= 1; -- i){
    	if(b[i] >= b[i - 1]){
    		a[i] = b[i - 1];
    	}
    	else{
    		a[i] = b[i];
    	}
    	s += a[i];
    }
    cout << s + b[0];

    return 0;
}

/*

*/


Measured memory_bytes: 3660
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
static const int MAX_LEN = 3000;

string s, t;
int memo[MAX_LEN + 1][MAX_LEN + 1];
int dir[MAX_LEN + 1][MAX_LEN + 1];

string dfs(string str, int y, int x){
	if(y == 0 || x == 0) return str;
	if(dir[y][x] == 0) return dfs(str + s[y - 1], y - 1, x - 1);
	if(dir[y][x] == 1) return dfs(str, y, x - 1);
	if(dir[y][x] == 2) return dfs(str, y - 1, x);
}

int main(){
	cin >> s >> t;
	for(int i = 0; i < s.length(); i++){
		for(int j = 0; j < t.length(); j++){
			if(s[i] == t[j]){
				memo[i + 1][j + 1] = max({memo[i][j] + 1, memo[i + 1][j], memo[i][j + 1]});
				if(memo[i][j] + 1 >= memo[i + 1][j] && memo[i][j] + 1 >= memo[i][j + 1]) dir[i + 1][j + 1] = 0;
				else if(memo[i + 1][j] >= memo[i][j + 1]) dir[i + 1][j + 1] = 1;
				else dir[i + 1][j + 1] = 2;
			}else{
				memo[i + 1][j + 1] = max(memo[i + 1][j], memo[i][j + 1]);
				if(memo[i + 1][j] >= memo[i][j + 1]) dir[i + 1][j + 1] = 1;
				else dir[i + 1][j + 1] = 2;
			}
		}
	}
	string res = dfs("", s.length(), t.length());
	reverse(res.begin(), res.end());
	cout << res << '\n';
	return 0;
}

Measured memory_bytes: 78336
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = 0
if n%2==0:
  ans+=a[0]
  for i in range((n-1)//2):
    ans+=2*a[1+i]
  print(ans)
else:
  ans+=a[0]
  for i in range((n-2)//2):
    ans+=2*a[1+i]
  ans+=a[2+i]
  print(ans)

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

const int INF = 1 << 30;

int N;
int h[100010];

int dp[100010];

int main() {
    cin >> N;
    for(int i = 0; i < N; i++)
        cin >> h[i];

    for(int i = 0; i < 100010; i++)
        dp[i] = INF;

    dp[0] = 0;
    for(int i = 1; i < N; i++) {
        dp[i] = min(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
        if(i - 2 >= 0) dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
    }

    cout << dp[N - 1] << endl;

    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define ll long long
using namespace std;
string s;bool vis[20];
ll ans;
ll check()
{
	ll nw=0,tot=0;
	for(int i=0;i<s.length();i++)
	{
		nw=nw*10+(s[i]-'0');
		if(vis[i])tot+=nw,nw=0;
	}
	tot+=nw;
	return tot;
}
void dfs(int pos)
{
	if(pos==s.length()-1)
	{
		ans+=check();
		return;
	}
	vis[pos]=1;dfs(pos+1);
	vis[pos]=0;dfs(pos+1);
}
int main()
{
	cin>>s;dfs(0);
	cout<<ans;
}

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

#define rep(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 print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]); if(i!=n-1) cout << " ";} cout << endl;
#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e18)
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
typedef pair<ll, ll> lpair;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,H,W;
    cin >> N >> H >> W;
    ll ans = (N - H + 1) * (N - W + 1);
    print(ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef ONLINE_JUDGE
#define endl "\n"
#endif
using namespace std;
typedef unsigned long long int lu;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> v;
typedef vector<lu> vu;
typedef vector<v> vv;
typedef vector<vu> vvu;
typedef vector<ld> vld;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef pair<ll, ll> pll;
typedef vector<set<ll>> vsll;
typedef set<pair<ll, ll>> spll;
typedef vector<spll> vspll;
typedef vector<pll> vpll;
typedef pair<lu, lu> puu;
typedef vector<puu> vpuu;
const ll MOD = 1000000007;
const ld PI = 2 * acos(0.0);
const v dx = {1, -1, 0, 0};
const v dy = {0, 0, 1, -1};
#define round(x, y) ((x + y - 1) / y)
#define ce(x, y) ((x + y - 1) / y)
#define amax(x, y) \
    if (y > x)     \
        x = y;
#define amin(x, y) \
    if (y < x)     \
        x = y;
#define lcm(x, y) ((x) * (y) / __gcd(x, y))
#define sz(x) (ll) x.size()
#define sq(x) ((x) * (x))
#define cb(x) ((x) * (x) * (x))
#define yes cout << "YES\n";
#define no cout << "NO\n";
#define yesno(f) \
    if (f)       \
        yes else no;
#define noo \
    { no return; }

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

template <typename T = ll>
vector<T> ga(ll n, bool oneIndexed = false) {
    vector<T> a = vector<T>(n + oneIndexed);

    for (ll i = 0; i < n; i++) {
        T p;
        cin >> p;
        a[i + oneIndexed] = p;
    }

    return move(a);
}

template <typename T, typename A>
void pa(vector<T, A> const &a, ll begin = 0, ll end = -1) {
    if (end == -1)
        end = sz(a) - 1;
    for (ll i = begin; i <= end; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

void solve() {
    ll n, w;
    cin >> n >> w;
    // val, weight
    vpll data(n);
    // min weight required to form i-th value
    v minWeight(1e5 + 1, 1e15);
    for (ll i = 0; i < n; i++) {
        cin >> data[i].second >> data[i].first;
    }

    sort(all(data));

    minWeight[0] = 0;
    for (ll j = 0; j < n; j++) {
        v x = minWeight;
        for (ll i = data[j].first; i <= 1e5; i++) {
            amin(x[i], minWeight[i - data[j].first] + data[j].second);
        }
        minWeight = x;
    }

    for (ll i = 1e5; i >= 0; i--) {
        if (minWeight[i] <= w) {
            cout << i;
            return;
        }
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("file", "r", stdin);
    // freopen("file", "w", stdout);
    solve();
    return 0;
}

Measured memory_bytes: 1792
import sys
from functools import reduce

def main():
    input = sys.stdin.readline
    N = int(input())
    As = list(map(int, input().split()))
    sign = reduce(lambda x, y: x * y, [int(a >= 0) * 2 - 1 for a in As])
    A_abs = [abs(a) for a in As]
    ans = sum(A_abs) if sign > 0 else sum(A_abs) - 2 * min(A_abs)
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 14908
#include <iostream>


using namespace std;

typedef pair<int,int> pii;

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

int w,h;
int mini;
pii start;

int exe(int data[20][20],int result[20][20],pii &now,int dir){   //場外,移動,ゴール　012
    int d[5]={-1,0,1,0,-1};

    rep(i,20)
        rep(j,20)
            result[i][j]=data[i][j];
    
    if( result[ now.first+d[dir] ][ now.second+d[dir+1] ]==1 )return -1;

    while( true ){
        now.first+=d[dir];
        now.second+=d[dir+1];
        if( !( 0<=now.first && now.first<h && 0<=now.second && now.second<w ) )return -1;
        if(data[now.first][now.second]==3)return 2;
        if(data[now.first][now.second]==1){
            result[now.first][now.second]=0;
            now.first-=d[dir];
            now.second-=d[dir+1];
            return 1;
        }
    }
}



void dfs(int data[20][20],pii now,int flor){
    if(flor>=11)return ;
    pii base;
    base.first=now.first;
    base.second=now.second;
    
    rep(i,4){
        now.first=base.first;
        now.second=base.second;
        
        int tmp[20][20]={};
        int res=exe(data,tmp,now,i);
        if(res==1) dfs(tmp,now,flor+1);
        else if(res==2){
            mini=min(mini,flor);
        }
    }
}




int main(){
    while(cin>>w>>h){
        pii now;
        mini=100000;
        int data[20][20]={};
        if(w==0 && h==0)break;
        
        rep(i,h){
            rep(j,w){
                cin>>data[i][j];
                if(data[i][j]==2){
                    start.first=i;
                    start.second=j;
                    data[i][j]=0;
                }
            }
        }
        
        
        now.first=start.first;
        now.second=start.second;
        
        
        dfs(data,now,1);
        if(mini==100000)mini=-1;
        cout<<mini<<endl;
    }
    
    
    return 0;
}

Measured memory_bytes: 1180
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner std = new Scanner(System.in);
        int n = std.nextInt();
        int W = std.nextInt();
        long[][] dp = new long[n + 1][W + 1];
        int[] w = new int[n];
        int[] v = new int[n];

        for (int i = 0; i < n; i++) {
            w[i] = std.nextInt();
            v[i] = std.nextInt();
        }

        dp[0][0] = 0;

        for (int i = 0; i < n; i++) {
            for (int sum_w = 0; sum_w <= W; sum_w++) {
                if (sum_w - w[i] >= 0) {
                    dp[i + 1][sum_w] = Math.max(dp[i][sum_w], dp[i][sum_w - w[i]] + v[i]);
                } else {
                    dp[i + 1][sum_w] = dp[i][sum_w];
                }
            }
        }

        System.out.println(dp[n][W]);
    }
}

Measured memory_bytes: 127572
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

struct UnionFind {
  vector<int> data;
  void init(int n) { data.assign(n, -1); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  bool same(int x, int y) { return root(x) == root(y); }
  bool unite(int x, int y) {
    x = root(x), y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
    return x != y;
  }
  int size(int x) { return -data[root(x)]; }
};

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(m), b(m);
  for (int i = 0; i < m; ++i) {
    cin >> a[i] >> b[i];
    a[i]--, b[i]--;
  }
  UnionFind uf;
  uf.init(n);
  ll res = 1ll * n * (n - 1) / 2;
  vector<ll> ans(m);
  for (int i = m - 1; i >= 0; --i) {
    ans[i] = res;
    if (!uf.same(a[i], b[i])) {
      res -= 1ll * uf.size(a[i]) * uf.size(b[i]);
      uf.unite(a[i], b[i]);
    }
  }
  for (int i = 0; i < m; ++i) {
    cout << ans[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define int long long
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define pii pair<int,int>
#define ff first
#define ss second
#define frr(i,n) for(int i=0;i<n;i++)
#define td(v) v.begin(),v.end()
#define inf 1000000000 // 1e9
#define M   1000000007 // 1e9 + 7
#define MAXN 21
using namespace std;
inline int mod(int n, int m){ int ret = n%m; if(ret < 0) ret += m; return ret; }
int gcd(int a, int b){return (b == 0 ? a : gcd(b, a%b));}
int exp(int a,int b,int m){
    if(b==0) return 1;
    if(b==1) return mod(a,m);
    int k = mod(exp(a,b/2,m),m);
    if(b&1){
        return mod(a*mod(k*k,m),m);
    }
    else return mod(k*k,m);
}
int n;
int dp[1<<MAXN][MAXN];
int can[MAXN][MAXN];

int solve(int id,int bitmask){
	//	cout<<id<<" "<<bitmask<<endl;
		if(id==n)return 1;
		if(dp[bitmask][id]!=-1)return dp[bitmask][id];
		int res=0;
		for(int i=0;i<n;i++){
			if((bitmask&(1<<i))==0 && can[id][i]){
				res=mod(res+solve(id+1,bitmask|(1<<i)),M);
			}
			
		}   	
	return dp[bitmask][id]=mod(res,M);
}


int32_t main(){
	fastio;
	memset(dp,-1,sizeof(dp));
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cin>>can[i][j];
	
	cout<<solve(0,0)<<endl;
}

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

using namespace std;

int main()
{
    string s;
    cin>>s;
    sort(s.begin(),s.end());
    if((s[0]==s[1]) && (s[2]==s[3]) && (s[0]!=s[2]) )
        cout<<"Yes";
    else
        cout<<"No";

cout<<endl;
    return 0;}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
typedef long long int LL;
const int MAX=1e9+7;
const int till=1e5+1;
int t[100005][2];

int main(){
	int n;
	int i,j,k;
	int a,b,c,d;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>a;
		t[a][i%2]++;
	}
	for(j=0,a=0,b=0;j<till;j++){
		if(t[j][0]>t[a][0])b=a,a=j;
		else if(t[j][0]>t[b][0])b=j;
	}
	for(j=0,c=0,d=0;j<till;j++){
		if(t[j][1]>t[c][1])d=c,c=j;
		else if(t[j][1]>t[d][1])d=j;
	}
	if(a==c){
		a=t[a][0]+t[d][1];
		b=t[b][0]+t[c][1];
		if(a<b)a=b;
	}else a=t[a][0]+t[c][1];
	cout<<n-a<<endl;
	return 0;
}


Measured memory_bytes: 1024
max_profit = -float('inf')
min_price = float('inf')

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

for t, price in enumerate(prices):
    if t > 0:
        max_profit = max(max_profit, price - min_price)
    min_price = min(min_price, price)

print(max_profit)


Measured memory_bytes: 13604
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int bingo[] = new int [9];
		boolean flag = false;

		//ビンゴカード作成
		for(int i = 0; i < 9; i++){
			bingo[i] = scan.nextInt();
		}

		//ビンゴカード穴開け
		int N = scan.nextInt();
		for(int k=0; k < N; k++){
			int num = scan.nextInt();
			for(int i=0; i < bingo.length; i ++){
				if(bingo[i] == num) bingo[i] = 0;
			}
		}

		//ビンゴチェック
		for (int i= 0; i <9; i +=3){
			if (bingo[i] == 0 && bingo[i+1] == 0 && bingo[i+2] == 0){
				flag = true;
			}
		}
		for(int i=0; i < 3; i ++){
			if (bingo[i] == 0 && bingo[i+3] == 0 && bingo[i+6] == 0){
				flag = true;
			}
		}
		if(bingo[0] == 0 && bingo[4] == 0 && bingo[8] == 0){
			flag = true;
		}
		if(bingo[2] == 0 && bingo[4] == 0 && bingo[6] == 0){
			flag = true;
		}

		if(flag){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}
}

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

int main() {
  string S;
  cin >> S;
  if (S.at(5) != '1' && 
      (S.at(6) == '1' || S.at(6) == '2' || S.at(6) == '3' || S.at(6) == '4')) {
    cout << "Heisei" << endl;
  }
  else cout << "TBD" <<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iterator>
#include <numeric>
#include <bitset>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
	int N;
	cin >> N;
	for (int i = 0; i <= 25; i++) {
		for (int j = 0; j <= 15; j++) {
			if (i * 4 + j * 7 == N) {
				cout << "Yes";
				return 0;
			}
		}
	}

	cout << "No";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
    ll a,b;
    cin>>a>>b;
    ll l=max(a,b),s=min(a,b),amari=l%s;
    while(amari!=0){
        l=s;
        s=amari;
        amari=l%s;
    }
    cout<<a/s*b;
}

Measured memory_bytes: 3640
#include "bits/stdc++.h"
#define   LF      '\n'
#define   ALL(x)  x.begin(), x.end()
#define   iostreamBooster()  do{cin.tie(nullptr);ios::sync_with_stdio(false);}while(0)
using namespace std;
typedef int64_t i64;
typedef pair<int,int> pii;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f'3f3f3f3fLL;


signed main()
{
  int A, B, K;
  cin >> A >> B >> K;

  vector<int> d;
  for (int i = 1; i <= min(A,B); ++i) {
    if (A % i == 0 && B % i == 0) d.push_back(i);
  }

  sort(rbegin(d), rend(d));
  cout << d[K-1] << endl;

  return 0;
}



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

int main() {
  int a, b, s=0;
  cin >> a >> b;
  
  for (; a <= b; a++) {
    int c, d, e, f, g;
    c = a / 10000;
    d = (a - c * 10000) / 1000;
    e = (a - c * 10000 - d * 1000) / 100;
    f = (a - c * 10000 - d * 1000 - e * 100) /10;
    g = (a - c * 10000 - d * 1000 - e * 100 - f * 10);
    if (c == g && d == f)
      s++;
  }
  
  cout << s << endl;
}

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


def bubble_sort(Ary):
    N = len(Ary)
    tento_su = 0
    flag = 1 # 0->整列済み
    while flag == 1: 
        flag = 0
        for i in range(N-1):
            if Ary[-1-i]<Ary[-2-i]:
                X = Ary[-1-i]
                Ary[-1-i] = Ary[-2-i]
                Ary[-2-i] = X
                flag = 1
                tento_su += 1
    return Ary, tento_su

A_sorted , tento_su = bubble_sort(A)
print(' '.join(map(str, A_sorted)))
print(tento_su)



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

int main(){
	int N;
  int X[100];
  cin>>N;
  int min_x=100;
  int max_x=0;
  
  for(int i=0;i<N;i++){
    cin>>X[i];
    if(X[i]<min_x)min_x=X[i];
    if(X[i]>max_x)max_x=X[i];
  }
  int sum=0,min_sum=-1;
  for(int j=min_x;j<=max_x;j++){
    for(int i=0;i<N;i++){
    	sum+=(j-X[i])*(j-X[i]);
  	}
    if(sum<min_sum ||min_sum<0){
      min_sum=sum;
    }
    sum=0;
  }
  cout<<min_sum<<endl;
    return 0;

}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  ll A, V, B, W, T;
  cin >> A >> V >> B >> W >> T;
  bool flag;
  if (B > A) {
    flag = (B + W * T) <= (A + V * T);
  } else {
    flag = (B - W * T) >= (A - V * T);
  }
  string ans = (flag) ? "YES" : "NO";
  cout << ans << endl;
  return 0;
}

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

using namespace std;

int main() {
	string s, t;
	cin >> s >> t;
	int n = s.length();
	while (n--){
		char temp = s[s.length() - 1];
		s.erase(s.end() - 1, s.end());
		s = temp + s;
		if (s == t){
			cout << "Yes";
			return 0;
		}
	}
	cout << "No";
	return 0;
}

Measured memory_bytes: 256