akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std; // 575

const int MAX = 3001;
int main() {
	string s, t;
	cin >> s >> t;
	static int dp[MAX][MAX];
	for (int i = 0;i <= s.size();++ i) for (int j = 0;j <= t.size();++ j) dp[i][j] = 0;
	for (int i = 1;i <= s.size();++ i) for (int j = 1;j <= t.size();++ j) dp[i][j] = min(max(dp[i - 1][j], dp[i][j - 1]) + (s[i - 1] == t[j - 1] ? 1 : 0), min(dp[i - 1][j - 1], dp[i][j - 1]) + 1);
	
	/*
	cout << "  ";
	for (int i = 0;i <= t.size();++ i) cout << (i == 0 ? ' ' : t[i - 1]) << " ";
	cout << endl;
	for (int i = 0;i <= s.size();++ i) {
		cout << (i == 0 ? ' ' : s[i - 1]) << " ";
		for (int j = 0;j <= t.size();++ j) cout << dp[i][j] << " ";
		cout << endl;
	}
	*/
	string ans = "";
	for (int i = s.size(), j = t.size();dp[i][j] > 0;-- j) {
		while (dp[i][j] == dp[i - 1][j]) -- i;
		while (dp[i][j] == dp[i][j - 1]) -- j;
		ans = t[j - 1] + ans;
	}
	cout << ans;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

        a b y x b
    : 0 0 0 0 0 0
a   : 0 1 1 1 1 1
ax  : 0 1 1 1 2 2
axy : 0 1 1 2 2 2
axyb: 0 1 2 2 2 3

               a v a d a k e d a v r a
:            0 0 0 0 0 0 0 0 0 0 0 0 0
a:           0 1 1 1 1 1 1 1 1 1 1 1 1
ab:          0 1 1 1 1 1 1 1 1 1 1 1 1
abr:         0 1 1 1 1 1 1 1 1 1 1 2 2
abra:        0 1 1 2 2 2 2 2 2 2 2 2 3
abrac:       0 1 1 2 2 2 2 2 2 2 2 2 3
abraca:      0 1 1 2 2 3 3 3 3 3 3 3 3
abracad:     0 1 1 2 3 3 3 3 4 4 4 4 4
abracada:    0 1 1 2 3 4 4 4 4 5 5 5 5
abracadab:   0 1 1 2 3 4 4 4 4 5 5 5 5
abracadabr:  0 1 1 2 3 4 4 4 4 5 5 6 6
abracadabra: 0 1 1 2 3 4 4 4 4 5 5 6 7
*/

Measured memory_bytes: 35456
#include <bits/stdc++.h>
#define repi(i, a, b) for (int i = (int)(a) ; i < (int)(b) ; i++)
#define rep(i, n) repi(i, 0, n)
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
struct Vec{
    double x, y;
};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
     return false;
}
template<class T>
T min(T a, T b)
{
    if (a < b) return a;
    return b;
}
template<class T>
T max(T a, T b)
{
    if (a > b) return a;
    return b;
}
using namespace std;
int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    // cout << fixed << setprecision(15);
    int X, i;
    cin >> X;
    int t = 599;

    repi(i,1, 9){
        if (X <= t){
            cout << 9 - i  << endl;
            break;
        } 
        t += 200;

        
    }
    return 0;
}



Measured memory_bytes: 3644
//
//AtCoder Beginner Contest 144
//C - Walk on Multiplication Table
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <functional>

using namespace std;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()

using ll = long long;
using ld = long double;

const double PI = 3.14159265358979323846;

ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }            //最小公倍数

int main()
{
    ll n;

    cin >> n;

    ll nn = sqrt(n);

    FORD(a, nn, 1){
        if (n%a == 0) {
            ll b = n/a;
            
            cout << a + b -2 << endl;
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define range(i,a,n) for(int i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}
void OUT(bool b){cout<<(b?"YES":"NO")<<endl;}
void Out(bool b){cout<<(b?"Yes":"No")<<endl;}
void out(bool b){cout<<(b?"yes":"no")<<endl;}
int popcnt(int x){return __builtin_popcount(x);}
int popcnt(ll x){return __builtin_popcountll(x);}
int bsr(int x){return 31 - __builtin_clz(x);}
int bsr(ll x){return 63 - __builtin_clzll(x);}
int bsf(int x){return __builtin_ctz(x);}
int bsf(ll x){return __builtin_ctzll(x);}

/*他のライブラリを入れる場所*/

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,p;
	cin>>n>>p;
	ll ans=1;
	for(ll i=2;i*i<=p;i++){
		if(p%i)continue;
		rep(j,n){
			if(p%i)goto x;
			else p/=i;
		}
		ans*=i;
		x:i--;
	}
	if(n==1)ans*=p;
	cout<<ans<<endl;
	return 0;
}

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

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

void init(int *a,int n){
  int i;
  for(i=0;i<n;i++) a[i]=0;
  return;
}

void run(void){
  char s[8001];
  scanf("%s",s);
  int len=0;
  while(s[len]!='\0') len++;
  int x,y;
  scanf("%d%d",&x,&y);
  int i;
  for(i=0;i<len && s[i]=='F';i++,x--);
  const int m=8001;
  int *dx=(int *)malloc(sizeof(int)*m);
  int *dy=(int *)malloc(sizeof(int)*m);
  int *tmp=(int *)malloc(sizeof(int)*m);
  init(dx,m);
  init(dy,m);
  dx[0]=1;
  dy[0]=1;
  int dir=1;
  while(i<len){
    if(s[i]=='T'){
      dir^=1;
      i++;
    } else {
      int k=0;
      while(i<len && s[i]=='F'){
	k++;
	i++;
      }
      init(tmp,m);
      if(dir){
	int j;
	for(j=0;j<m-k;j++){
	  if(dx[j]){
	    tmp[ABS(j-k)]=1;
	    tmp[j+k]=1;
	  }
	}
	int *swap=dx;
	dx=tmp;
	tmp=swap;
      } else {
	int j;
	for(j=0;j<m-k;j++){
	  if(dy[j]){
	    tmp[ABS(j-k)]=1;
	    tmp[j+k]=1;
	  }
	}
	int *swap=dy;
	dy=tmp;
	tmp=swap;
      }
    }
  }
  printf("%s\n",dx[ABS(x)]==1 && dy[ABS(y)]==1?"Yes":"No");
}

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


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

int main() {
  int N;
  cin >> N;
  int64_t sum = 0;
  
  for (int i = 1; i <= N; i++) {
    int64_t num = N / i;
    sum += i * (num + 1) * num / 2;
  }
  cout << sum << endl;
}

  

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<LL,LL>
#define x first
#define y second
#define N 131072
#define pi acos(-1)
#define sqr(x) ((x)*(x))
#define pdd pair<double,double>
#define MEMS(x) memset(x,-1,sizeof(x))
#define MEM(x) memset(x,0,sizeof(x))
int main(){
    int n,x;
    scanf("%d %d",&n,&x);
    LL b[100005],l[100005],u[100005];
    LL sum=0;
    vector<pair<LL,pll> > v;
    for(int i=0;i<n;i++){
        scanf("%lld %lld %lld",&b[i],&l[i],&u[i]);
        sum+=b[i]*l[i];
        v.pb(mp(b[i]*l[i]+u[i]*x-b[i]*u[i],mp(u[i],l[i])));
       // printf("%d %d\n",v.back().x,v.back().y);
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    LL ans=0;
    LL temp=0;
    int i;
    for(i = 0;i<v.size();i++){
        if(temp+v[i].x>sum){
            break;
        }
        temp+=v[i].x;
        ans+=x;
    }
    int ttemp=i;
    LL Max=0;
    if(i==v.size()){
        Max=x;
    }
    for(;i<v.size();i++){
        Max=max(Max,(v[i].x-(sum-temp))/v[i].y.x);
    }
    temp+=v[ttemp].x;
    for(int j=0;j<ttemp;j++){
        Max=max((temp-sum)/v[j].y.x,Max);
    }
    LL ans1=ans+x-Max;
    temp-=v[ttemp].x;
    LL add = x;
    for(int j=ttemp;j<v.size();j++){
        add=min(add,(sum-temp+v[j].y.y-1)/v[j].y.y);
    }
    temp+=v[ttemp].x;
    for(int j =0;j<ttemp;j++){
        LL mytemp=temp-v[j].x;
        add = min(add,(sum-mytemp+v[j].y.y-1)/v[j].y.y);
    }
    LL ans2=ans+add;
   //printf("%lld %lld\n",ans1,ans2);
    printf("%lld\n",min(ans1,ans2));
}
/*
230
0.5 0.5
0.5 0.25
0.25 0.125
0.25
*/

Measured memory_bytes: 6516
#include<bits/stdc++.h>
#define LL long long
#define REP(i,n) for(int i=0;i<(n);++i)
#define PER(i,n) for(int i=n-1;i>=0;--i)
#define REPA(i,n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define PII pair<int,int>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define MOD ((LL)1e9+7) 
#define INF ((int)1e9+7)
#define INFLL ((LL)1e18)
#define ALL(x) (x).begin(),(x).end()
#define BIT(x) (1LL << (x))
using namespace std;

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

LL modpow(LL x, LL b){
	LL res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

LL modinv(LL x){
	if(x<=0)return 0;
	LL res = 0;
	PER(i, 40){
		if(x&BIT(i)){
			if(i==0)res ^= x;
			else res ^= BIT(i+1) - 1;
		}
	}
}

LL func(LL x){
	if(x<=0)return 0;
	LL res = 0;
	PER(i, 40){
		if(~x&BIT(i))continue;
		if(i==0){
			res ^= x;
			continue;
		}
		if(i==1){
			res ^= 3;
			continue;
		}
		res ^= BIT(i);
	}

	return res;
}


int main(){
	LL A, B;
	cin >> A >> B;
	cout << (func(B)^func(A-1)) << endl;

	return 0;
}


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

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

	int n, k;
	cin >> n >> k;
	vector<int> v(n), dp(n);
	for (auto& i : v) cin >> i;
	dp[0] = 0;
	for (int i = 1; i < n; i++) {
		int j = max(0, i - k);
		dp[i] = dp[j] + abs(v[i] - v[j]);
		for (; j < i; j++) {
			dp[i] = min(dp[i], dp[j] + abs(v[i] - v[j]));
		}
	}
	cout << dp[n - 1];
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
 
using namespace std;
 
int main (){
  
  long long int a,b;
  char d,e;
  string c[30][30];
  
  
  cin >>a >>b ;
  for(int i=0;i<=a;i++){
    for(int j=0;j<b;j++)
  cin >> c[i][j];
    
  }
  d ='A';
  for(int i=0;i<=a;i++){
    for(int j=0;j<b;j++)
      if( c[i][j] == "snuke"){
        d += j;
        cout << d<<i+1<< endl;
      }
  }
}
  
   
  
  
 


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define _for(i,a,b) for(int i=a;i<=b;i++)
const int maxn = 55699;
int n,sum,prime[maxn],isprime[maxn],ans[maxn];
void ge()
{
    _for(i,2,maxn)
    {
        if(prime[i]==0)
        {
            isprime[++sum]=i;
            for(int j=i*2;j<=maxn;j+=i)prime[j]=1;
        }
    }
}
int main(int argc, char const *argv[])
{
    cin>>n;
    ge();
    int k = 0;
    _for(i,1,sum)
    {
        if(isprime[i]%5==1)
        {
            cout<<isprime[i]<<" ";
            k++;
        }
        if(k==n)
        {
            cout<<endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 512
N = int(input())
P = list(map(int, input().split()))

cnt = 0
t = 'o' if P[0] == 1 else 'x'
j = 0 if t == 'o' else 1
L = []
for i, p in enumerate(P):
    s = 'o' if p == (i + 1) else 'x'
    if s == t:
        cnt += 1
    else:
        L.append(cnt)
        cnt = 1
        t = s
L.append(cnt)

ans = 0
for i, n in enumerate(L):
    if i % 2 == j:
        ans += (n + 2 - 1) // 2

print(ans)


Measured memory_bytes: 14008
def main():
    N = int(input())
    ans = ['a']
    i = 0
    while i != N-1:
        tmp = set()
        i += 1
        for j in range(len(ans)):
            for k in range(i+1):
                tmp.add(ans[j]+chr(97+k))
                if chr(97+k) not in ans[j]:
                    break
        ans = list(tmp)
    ans.sort()
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

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

int binary(long* S, long* T, int n, int q) {
    long a[100000];
    int left, mid, right;
    int count = 0;
    
    for(int i = 0; i < q; ++i) {
        left = 0;
        right = n;
        while(left < right) {
            mid = (left + right) / 2;
            if(T[i] == S[mid]) {
                bool flag = true;
                for(int j = 0; j < count; ++j) {
                    if(a[j] == T[i]) {
                        flag = false;
                    }
                }
                if(flag) {
                    a[count] = T[i];
                    ++count;
                    break;
                }
            } else if(T[i] < S[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
    }
    return count;
}

int main(void) {
    int n, q;
    long S[100000];
    long T[100000];
    
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> S[i];
    }
    
    cin >> q;
    for(int i = 0; i < q; ++i) {
        cin >> T[i];
    }
    
    cout << binary(S, T, n, q) << endl;
}



Measured memory_bytes: 4252
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define inf 1000000007
using namespace std;
typedef pair<ll, ll>P;
ll gcd(ll x, ll y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
ll lcm(ll x, ll y) {
	return x * y / gcd(x, y);
}
ll dp[114][10];
ll f[114];
signed main() {
	ll h, w, k;
	cin >> h >> w >> k;
	f[0] = 1;
	f[1] = 1;
	for (int i = 2; i <= 110; i++)f[i] = f[i - 2] + f[i - 1];
	dp[0][0] = f[w - 1];
	dp[0][1] = f[w - 2];
	for (int i = 0; i < h - 1; i++) {
		for (ll j = 0; j < w; j++) {
			if(j-1>=0)dp[i+1][j-1]+=dp[i][j]*f[max((ll)0,j-1)]*f[max((ll)0,w-j-1)];
			if(j+1<w)dp[i+1][j+1]+=dp[i][j]*f[max((ll)0,j)]*f[max((ll)0,w-j-2)];
			dp[i+1][j]+=dp[i][j]*f[max((ll)0,j)]*f[max((ll)0,w-j-1)];
			dp[i + 1][j - 1] %= inf;
			dp[i + 1][j] %= inf;
			dp[i + 1][j + 1] %= inf;
		}
	}
	cout << dp[h - 1][k - 1] % inf << endl;
	getchar(); getchar(); return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
  int i, n, t, start, a[200010]={0};
  long long c = 0;
  scanf("%d %d", &n, &t);

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

 if(n == 1){
    printf("%d\n", t);
    return 0;
  }

  for(i = 0; i < n; i++){
    if(a[i+1]-a[i] < t  && i != n-1)
      c += a[i+1]-a[i];
    else c += t;
  }
  printf("%lld\n", c);
  return 0;
} 

Measured memory_bytes: 896
import java.util.*;
public class Main{
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  long ans=0;
  long a[]=new long[100001];
  long k=Long.parseLong(sc.next());
  for(int i=0;i<n;i++){
  	int po=sc.nextInt();
  	a[po]+=sc.nextInt();
  }
  for(int i=0;i<100001;i++){
  	ans+=a[i];
    if(ans>=k){
    System.out.println(i);
      break;
    }
  }}
}


Measured memory_bytes: 84040
import bisect
N,M,K = map(int, input().split())
A= list(map(int, input().split()))
B = list(map(int, input().split()))
for i in range(1,len(A)):
    A[i]+=A[i-1]
for i in range(1,len(B)):
    B[i]+=B[i-1]

honn=bisect.bisect(B,K)
#print(honn)
for i in range(len(A)):
    s=K-A[i]
    if s>=0:
        
        a=bisect.bisect(B,s)
        #print(s)
        if i+1+a>honn:
            honn=i+1+a
print(honn)

Measured memory_bytes: 40588
class Tree(object):
    def __init__(self):
        self.nodes = {}
        self.root = None

    def add_node(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)

    def add_child(self, parent_id, child_id):
        self.add_node(parent_id)
        self.add_node(child_id)
        self.nodes[parent_id].add_child(self.nodes[child_id])

    def set_depth(self):
        for node in self.nodes.values():
            if node.type == 'root':
                self.root = node
                break
        self.root._set_depth(0)

    def set_height(self):
        # メモ化して再帰する
        self.root._set_height()


class Node(object):
    def __init__(self, id):
        self.id = id
        self.parent = None
        self.children = []
        self.depth = None
        self.height = None
        self.type = 'root'
        self.bro = None

    def add_child(self, child):
        child.bro = len(self.children)
        self.children.append(child)
        child.parent = self
        child.update_nodetype()
        if self.parent:
            self.update_nodetype()

    def update_nodetype(self):
        if self.parent:
            if self.children:
                self.type = 'internal node'
            else:
                self.type = 'leaf'
        else:
            self.type = 'root'

    def _set_depth(self, depth):
        self.depth = depth
        for child in self.children:
            child._set_depth(depth+1)

    def _set_height(self):
        # メモ化再帰
        if not self.children:
            self.height = 0
        else:
            if self.height:
                pass
            else:
                height = 0
                for child in self.children:
                    child._set_height()
                    height = max(child.height, height)
                self.height = height + 1

    def get_sib(self):
        if not self.parent:
            return -1
        else:
            bros = self.parent.children
            if len(bros) == 1:
                return -1
            else:
                if self.bro == 0:
                    return bros[1].id
                else:
                    return bros[0].id

    def __str__(self):
        parent = self.parent.id if self.parent else -1
        sib = self.get_sib()
        deg = len(self.children)
        dep = self.depth
        h = self.height
        str = 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(id, parent, sib, deg, dep, h, self.type)
        return str


tree = Tree()
n = int(input())
for i in range(n):
    tmp = list(map(int, input().split()))
    id = tmp[0]
    children = tmp[1:]
    tree.add_node(id)
    for c in children:
        if c != -1:
            tree.add_child(id, c)
tree.set_depth()
tree.set_height()
for id in range(n):
    print(tree.nodes[id])



Measured memory_bytes: 5616
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int A,N,K,o[2000],t[2000];
int w[2001][2001];
int inf=1e9;
int dp[2001][2001];

int mni[2000];
void minima(int d,int ia,int ib,int ja,int jb){	//[ia,ib]*[ja,jb]
	if(ia>ib) return;
	if(ia==ib){
		int mn=0,id=-1;
		for(int j=ja;j<=jb;j++){
			int tmp=dp[j][d]+w[j+1][ia];
			if(id<0||mn>tmp) id=j,mn=tmp;
		}
		mni[ia]=id;
		return;
	}
	int im=(ia+ib)/2;
	minima(d,im,im,ja,jb);
	minima(d,ia,im-1,ja,mni[im]);
	minima(d,im+1,ib,mni[im],jb);
}
int main(){
	rep(i,2001) rep(j,2001) dp[i][j]=inf;
	cin>>A>>N>>K;
	rep(i,A) cin>>o[i];
	rep(i,N){
		int x,y;
		cin>>x>>y;
		t[i]=x-o[y-1];
	}
	sort(t,t+N);
	rep(r,N){
		for(int l=r-1;l>=0;l--){
			w[l][r]=w[l+1][r]+t[r]-t[l];
		}
	}
	rep(i,N) dp[i][0]=w[0][i];
	rep1(d,K-1){
		minima(d-1,0,N-1,0,N-1);
		rep(i,N){
			int j=mni[i];
			dp[i][d]=dp[j][d-1]+w[j+1][i];
		}
	}
	cout<<dp[N-1][K-1]<<endl;
}

Measured memory_bytes: 32580
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

h, w = na()
n = ni()
a = na()

ans = [[0] * w for _ in range(h)]
cur = 0
for i in range(h):
    if i % 2 == 0:
        for j in range(w):
            ans[i][j] = cur + 1
            a[cur] -= 1
            if a[cur] == 0:
                cur += 1
    else:
        for j in range(w - 1, -1, -1):
            ans[i][j] = cur + 1
            a[cur] -= 1
            if a[cur] == 0:
                cur += 1

for i in range(h):
    print(*ans[i], sep=" ")

Measured memory_bytes: 3952
#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 ALL(v) begin(v),end(v)
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

int N, M;
vector<pii> g[50];
int U[20], V[20];
int ins[50]; // iを黒くしたときに満たされる制約の集合
pii par[50];

void dfs(int u, int p) {
	for (pii e : g[u]) {
		int v = e.fi;
		if (v == p) continue;
		par[v] = pii(u, e.se);
		dfs(v, u);
	}
}

int main() {
	cin >> N;
	REP(i, N - 1) {
		int a, b;
		scanf("%d %d", &a, &b);
		--a; --b;
		g[a].emplace_back(b, i);
		g[b].emplace_back(a, i);
	}
	cin >> M;
	REP(i, M) scanf("%d %d", U + i, V + i), --U[i], --V[i];
	
	REP(i, M) {
		// U[i] -> V[i]
		fill(par, par + N, pii(-1, -1));
		dfs(U[i], -1);
		
		int u = V[i];
		while (par[u].fi != -1) {
			ins[par[u].se] |= 1<<i;
			u = par[u].fi;
		}
	}
	
	ll ans = 1ll<<(N-1);
	FOR(s, 1, 1<<M) {
		// 制約 i ∈ s は満たされない
		int pcnt = 0;
		REP(i, M) if (s >> i & 1) ++pcnt;
		
		int ok = 0;
		REP(i, N - 1) if (!(ins[i] & s)) ++ok;
		ll cur = 1ll<<ok;

		if (pcnt & 1) cur = -cur;
		ans += cur;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int par[100005];
int ra[100005];
void init(int n){
  for(int i=0;i<n;i++){
    par[i]=i;
    ra[i]=0;
  }
}
int find(int x){
  if(par[x]==x){
    return x;
  }
  else{
    return par[x]=find(par[x]);
  }
}
void unite(int x,int y){
  x=find(x);
  y=find(y);
  if(x==y)return;
  if(ra[x]<ra[y]){
    par[x]=y;
  }
  else{
    par[y]=x;
    if(ra[x]==ra[y])ra[x]++;
  }
}
bool same(int x,int y){
  return find(x)==find(y);
}

int main(){
  int n,m;
  cin >> n >> m;
  init(n);
  for(int i=0;i<m;i++){
    int a,b;
    cin >> a >> b;
    unite(a,b);
  }
  int q;
  cin >> q;
  for(int i=0;i<q;i++){
    int a,b;
    cin >> a >> b;
    if(same(a,b))cout << "yes" << endl;
    else cout << "no" << endl;
  }
  return 0;
}

Measured memory_bytes: 3788
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#include <fstream>
#include <random>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <functional>
#include <random>
#include <time.h>
#include <chrono>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <limits>
#include <numeric>
#include <type_traits>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define MOD 1000000007
#define SORT(s) sort(s.begin(), s.end());
#define REVERSE(s) reverse(s.begin(), s.end());
#define SUM(s) accumulate(s.begin(), s.end(), 0);
#define P pair<int,int>
#define mp make_pair
#define valid(x,y,h,w) (0<=x&&x<h&&0<=y&&y<w)
//#define int ll
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int ndx[8] = { 0,1,0,-1, 1,1,-1,-1 };
int ndy[8] = { 1,0,-1,0, 1,-1,-1,1 };
using namespace std;
int POW(int x, int y) { return int(pow(double(x), double(y))); }
double log(double a, double b) { return log(b) / log(a); }

template <class T>
void VecRowShow(vector<T> vec) {
	rep(i, vec.size()) {
		if (i != vec.size() - 1) cout << vec[i] << " ";
		else cout << vec[i] << endl;
	}
}

int main() {
	int n, k, c;
	cin >> n >> k >> c;
	string s;
	cin >> s;
	vector<int> a(n), b(n);

	if (n == 1) {
		cout << 1 << endl;
		return 0;
	}

	rep(i, n) {
		if (i - c - 1 < 0) {
			if (s[i] == 'o') {
				a[i] = 1;
			}
			else {
				if (i == 0) {
					a[i] = 0;
				}
				else {
					a[i] = a[i - 1];
				}
			}
		}
		else {
			if (s[i] == 'o') {
				a[i] = a[i - c - 1] + 1;
			}
			else {
				a[i] = a[i - 1];
			}
		}
	}

	REVERSE(s);
	rep(i, n) {
		if (i - c - 1 < 0) {
			if (s[i] == 'o') {
				b[i] = 1;
			}
			else {
				if (i == 0) {
					b[i] = 0;
				}
				else {
					b[i] = b[i - 1];
				}
			}
		}
		else {
			if (s[i] == 'o') {
				b[i] = b[i - c - 1] + 1;
			}
			else {
				b[i] = b[i - 1];
			}
		}
	}
	REVERSE(b);



	vector<int> ans;
	rep(i, n) {
		if (i == 0) {
			if (b[1] < k) {
				ans.push_back(i + 1);
			}
		}
		else if (i == n - 1) {
			if (a[i - 1] < k) {
				ans.push_back(i + 1);
			}
		}
		else {
			if (a[i - 1] + b[i + 1] < k) {
				ans.push_back(i + 1);
			}
		}
	}

	rep(i, ans.size()) {
		cout << ans[i] << endl;
	}
	if (ans.size() == 0)
		cout << endl;
}



Measured memory_bytes: 4216
import java.io.File;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

public class Main {
 
	public static void main(String[] args) throws IOException {
		//File file = new File("input.txt");
		//Scanner sc = new Scanner(file);
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		String[] s = new String[N];
		for(int i = 0; i < N; i++) s[i] = sc.next();
		int M = sc.nextInt();
		String[] t = new String[M];
		for(int i = 0; i < M; i++) t[i] = sc.next();
		
		HashMap<String,Integer> map = new HashMap<String,Integer>();
		
		for(int i = 0; i < N; i++){
			if(map.containsKey(s[i])) map.put(s[i], (map.get(s[i]).intValue()+1));
			else map.put(s[i],1);
		}		
		
		for(int i = 0; i < M; i++){
			if(map.containsKey(t[i])) map.put(t[i],map.get(t[i])-1);
		}
				
		ArrayList<Integer> coll = new ArrayList<Integer>(map.values());
		
		//for(String ss : map.keySet()) System.out.println(ss);
		//for(Integer ii : map.values()) System.out.println(ii);
		Integer ii = Collections.max(coll);
		System.out.println((ii<0)?0:ii);
		
	}
}

Measured memory_bytes: 21712
#pragma region Macros
#include <bits/stdc++.h>
#define int long long
using ll = long long;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(ll i = ll(a); i < ll(b+a); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define all(a) (a).begin(), (a).end()
using namespace std;
using P = pair<int, int>;
#define SZ(x) ((int)(x).size())
#define bit(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#pragma endregion

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

  int s,w; cin >> s >> w;

  if (s>w)
    cout << "safe" << endl;
  else
    cout << "unsafe" << endl;

  return 0;
}


Measured memory_bytes: 3568
#include <set>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <limits>
#include <map>
#include <numeric>

#define ll long long
using namespace std;
static ll imin = std::numeric_limits<ll>::min();
static ll imax = std::numeric_limits<ll>::max();
#define rep(i, n) for(int i = 0; (i)<(n); ++(i))
#define rep1(i, n) for(int i = 1; (i)<(n); ++(i))
#define rev_rep(i, n) for(int i = (n) - 1; (i) >= 0; --(i))
#define range(a, i, b) for(int i = (a); (i) < (b); ++(i))
#define dump(x) cout << #x << ":" << x << "\n";
#define all(v) v.begin(), v.end()
#define readl(N) ll N; cin >> N
#define readlv(N, vec) vector<ll> vec(N); rep(i, N){cin >> vec[i];}
#define greater_than [](ll l, ll r){return l > r;}
template<class T1, class T2>
std::ostream& operator << (std::ostream& os, std::map<T1, T2>& mp);
template<class T1, class T2>
std::ostream& operator << (std::ostream& os, std::pair<T1, T2>& pair);
template<class T>
std::ostream& operator << (std::ostream& os, std::vector<T>& vec);
template<class T1, class T2>
std::ostream& operator << (std::ostream& os, std::pair<T1, T2>& pair){
  os << '(' << pair.first << ',' << pair.second << ')';
  return os;
}

template<class T>
std::ostream& operator << (std::ostream& os, std::vector<T>& vec){
  std::size_t n = vec.size();
  if(n == 0){
    return os;
  }
  os << " ";
  for(ll i = 0; i<n - 1; ++i){
    os << vec[i] << " ";
  }
  os << vec[n - 1];
  os << std::endl;
  return os;
}

template<class T1, class T2>
std::ostream& operator << (std::ostream& os, std::map<T1, T2>& mp){
  std::size_t n = mp.size();
  if(n == 0){
    return os;
  }
  os << " ";
  for(auto && x:mp){
    os << x << " ";
  }
  os << std::endl;
  return os;
}

template<class T>
std::ostream& operator << (std::ostream& os, std::set<T>& mp){
  std::size_t n = mp.size();
  if(n == 0){
    return os;
  }
  os << " ";
  for(auto && x:mp){
    os << x << " ";
  }
  os << std::endl;
  return os;
}

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

#ifndef BOOST_TEST_MAIN
int main(int const argc, char const** argv){
  readl(n); readl(m);
  vector<ll> x(m);
  rep(i, m){
    cin >> x[i];
  }

  sort(all(x));
  // dump(x);

  vector<ll> y(m - 1);
  rep(i, m - 1){
    y[i] = x[i + 1] - x[i];
  }
  sort(all(y));
  // dump(y);
  ll res = 0;
  rep(i, m - n){
    res += y[i];
  }
  cout << res;
}
#endif


Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF = 2e9;
#define LINF = 1e18;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define dump(x) cout << #x << = << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO")
#define Yes(n) cout << ((n) ? "Yes" : "No")

void input(vector<int> x, auto n){
   rep(i,n)cin >> x[i];
}

int main(){
    int a,b,c;
    cin >> a >> b >> c;

    int ans = 0;
    for(int i = a; i <= b; i++){
        if(!(c%i))ans++;
    }

    cout << ans << endl;
}


Measured memory_bytes: 3088
s = list(input())

for i in range(2**3):
    cnt = int(s[0])
    ls = []
    for j in range(3):    
        if ((i>>j)&1):
            ls.append("+")
            cnt += int(s[j+1])
        else:
            ls.append("-")
            cnt -= int(s[j+1])
    if cnt==7:
        eq = [s[0],ls[0],s[1],ls[1],s[2],ls[2],s[3],"=7"]
        print("".join(eq))
        break


Measured memory_bytes: 38384
n, m = map(int, input().split())

to = [[] for i in range(n + 1)]


for i in range(m):
    a, b = map(int, input().split())
    to[a].append(b)
    to[b].append(a)

ans = [-1] * (n+1)


import collections
q = collections.deque([1])

while q:
    now = q.popleft()
    for t in to[now]:
        if ans[t] == -1:
            q.append((t))
            ans[t] = now

if (-1) in ans[2:]:
    print('No')
else:
    print('Yes')
    for a in ans[2:]:
        print(a)


Measured memory_bytes: 34776
#include<bits/stdc++.h>
#define P pair<int,int>
using namespace std;
const int N=2e5+5;
int t,n,k[N],l[N],r[N];
priority_queue<P,vector<P>,greater<P> >q;
int a[N],cnta;
long long ans=0;
bool cmp1(int x,int y){
    return k[x]<k[y];
}
bool cmp2(int x,int y){
    return k[x]>k[y];
}
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>k[i]>>l[i]>>r[i];
        cnta=0;
        for(int i=1;i<=n;i++)if(l[i]>r[i])a[++cnta]=i;
        sort(a+1,a+cnta+1,cmp1);
        for(int i=1;i<=cnta;i++){
            int now=a[i];
            if(q.size()<k[now])q.push(P(l[now]-r[now],now)),ans+=l[now];
            else{
                if(q.empty()){
                    ans+=r[now];
                    continue;
                }
                int x=q.top().second;q.pop();ans-=l[x];
                if(l[x]-r[x]>l[now]-r[now])q.push(P(l[x]-r[x],x)),ans+=l[x]+r[now];
                else q.push(P(l[now]-r[now],now)),ans+=r[x]+l[now];
            }
        }
      //  cout<<ans<<endl;
        while(!q.empty())q.pop();
        for(int i=1;i<=n;i++)if(l[i]==r[i])ans+=l[i];
        cnta=0;
        for(int i=1;i<=n;i++)if(l[i]<r[i])a[++cnta]=i;
        sort(a+1,a+cnta+1,cmp2);
      //  for(int i=1;i<=cnta;i++)cout<<a[i]<<" ";cout<<endl;
        for(int i=1;i<=cnta;i++){
            int now=a[i];
            if(q.size()<n-k[now])q.push(P(r[now]-l[now],now)),ans+=r[now];
            else{
                if(q.empty()){
                    ans+=l[now];
                    continue;
                }
                int x=q.top().second;q.pop();ans-=r[x];
                if(r[x]-l[x]>r[now]-l[now])q.push(P(r[x]-l[x],x)),ans+=r[x]+l[now];
                else q.push(P(r[now]-l[now],now)),ans+=l[x]+r[now];
            }
        }
        while(!q.empty())q.pop();
        cout<<ans<<endl;
        ans=0;
    }
    return 0;
}


Measured memory_bytes: 6936
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF 1e18L
#define INF 1e9L
#define EPS 1e-9
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<int>())S
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define pb push_back
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
typedef long long ll;
typedef pair<int, int> pii;

int main(void)
{
    int a,b;
    cin >> a >> b;
    pr(a%b==0?0:1);
}

Measured memory_bytes: 256
/// kAAzuki Hoshino
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#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;
#define int long long
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define inf 1000000000
#define mod 1000000007
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define rep1(i, a, b) for(int i =a; i >=b; i--)
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}

int n,pre[111111], suf[111111], a[111111], ans;

signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

  cin >> n;
  for(int i=1;i<=n;i++)cin >> a[i];
  for(int i=1;i<=n;i++)pre[i] = __gcd(pre[i-1], a[i]);
  for(int i=n;i>=1;i--)suf[i] = __gcd(suf[i+1], a[i]);

  for(int i=1;i<=n;i++){
    ans = max( ans, __gcd( suf[i+1], pre[i-1] ) );
  }

  cout << ans << endl;

return 0;
}
///....


Measured memory_bytes: 2560
import java.util.Scanner;

class Main {

    private static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int a = sc.nextInt(), b = sc.nextInt();
        if ((a + b) % 2 == 0) {
            System.out.println((a + b) / 2);
        } else {
            System.out.println((a + b) / 2 + 1);
        }
    }
}

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


typedef pair< int , int > Pi;
typedef pair< int , Pi > Pii;

typedef long long int64;
const int INF = 1 << 30;
int N, M;


class DisjointSet{
private:
  vector<int> rank, p;
  void link(int x,int y){
    if(rank[x] > rank[y]){
      p[y] = x;
    }else{
      p[x] = y;
      if(rank[x] == rank[y]) rank[y]++;
    }
  }
public:
  DisjointSet(){}
  DisjointSet(int size){
    rank.resize(size,0);
    p.resize(size,0);
  }
  void makeSet(int x){
    p[x] = x, rank[x] = 0;
  }
  void Union(int x,int y){
    link(findSet(x),findSet(y));
  }
  int findSet(int x){
    return( x != p[x] ? p[x] = findSet(p[x]) : p[x]);
  }
};

struct edge{
  int u, v, cost;
  bool operator<(const edge& hoge)const{
    return cost < hoge.cost;
  }
};
typedef vector< edge > Edges;
pair< bool, int > kruskal( DisjointSet& uf_tree, Edges& edges, vector< bool >& foo){
  int ret = 0;
  for(int i = 0; i < edges.size(); i++){
    edge& e = edges[i];
    if(foo[e.u] && foo[e.v] && uf_tree.findSet(e.u) != uf_tree.findSet(e.v)){
      uf_tree.Union( e.u, e.v);
      ret += e.cost;
    }
  }
  for(int i = 0; i < N; i++){
    if(foo[i])
      for(int j = i + 1; j < N; j++){
        if(foo[j] && uf_tree.findSet(i) != uf_tree.findSet(j)){
          return make_pair( false, ret);
        }
      }
  }
  return make_pair(true,ret);
}

int main(){
  vector< Pi > h;
  vector< edge > edges;

  while(cin >> N >> M, N){
    h.resize(N);
    edges.resize(M);
    DisjointSet uf_tree(N);
    for(int i = 0; i < N; i++){
      uf_tree.makeSet(i);
    }

    for(int i = 0; i < N; i++){
      cin >> h[i].first;
      h[i].second = i;
    }
    sort(h.begin(), h.end());
    for(int i = 0; i < M; i++){
      int a, b, c;
      cin >> a >> b >> c;
      a--, b--;
      edges.push_back((edge){ a, b, c});
      edges.push_back((edge){ b, a, c});
    }
    sort( edges.begin(), edges.end());
    int ret = 0;
    vector< bool > foo;
    foo.resize(N, false);
    foo[h[N - 1].second] = true;
    for(int i = N - 2; i >= 0; i--){
      int time = h[i].first;
      int j = i;
      while(j >= 0 && time == h[j].first){
        foo[h[j].second] = true;
        j--;
      }
      while(i >= 0 && time == h[i].first){
        Pi cost = kruskal( uf_tree, edges, foo);
        ret += cost.second;
        if(!cost.first){
          uf_tree = DisjointSet(N);;
          for(int i = 0; i < N; i++){
            uf_tree.makeSet(i);
          }
          ret = 0;
        }
        i--;
      }
      i++;
    }

    
    cout << ret << endl;
    edges.clear();
  }
}

Measured memory_bytes: 2092
#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
#define pii pair<int,int>
#define pll pair<long long,long long>
#define usi unordered_set<int>
#define usl unordered_set<long long>
#define umii unordered_map<int,int>
#define umsi unordered_map<string,int>
#define umll unordered_map<long long,long long>
#define fi first
#define sec second
#define pub push_back
#define pob pop_back
#define B begin
#define E end
#define mp make_pair
#define vi vector<int>
#define vl vector<long long>
#define vii vector<pii>
#define vll vector<pll>
#define deb(x) cout<<#x<<": "<<x<<"\n"
#define endl '\n'
#define PIE 3.141592653
#define MOD 1000000007
#define f(i,a,b,c) for(ll i=a;i<=b;i+=c)
#define frev(i,n,b,c)  for(ll i=n;i>=b;i-=c)
const ll inf = 1000000000000000000;
using namespace std;
 
//            < = = = = =    GCD     = = = = = >
 
ll gcd(ll a,ll b)
{
	if(a<b)	gcd(b,a);
	if(b==0)	return a;
	return gcd(b,a%b);
}
 
//            < = = = = =    LCM     = = = = = >
 
ll lcm(ll a,ll b) 
{ 
	ll x=(a/gcd(a,b))*b; 
	return x;
}
 
//            < = = = = =    power  x^n     = = = = = >
 
ll power(ll x , ll n , ll m=inf){
	if(x==0){
		return 0;
	}
	if(n==0){
		return 1;
	}
	ll ans;
	if(n%2==0){
		ll smallAns = power(x,n/2,m);
		ans = (smallAns*smallAns)%m;		
	} else {
		ll smallAns = power(x,n-1,m);
		ans = x;
		ans = (ans*smallAns)%m;
	}
	// for negative values also
	return (ans+m)%m;
	
}
 
//            < = = = = =    CHECK FOR PRIME     = = = = = >
 
bool isprime(int n){
   if(n==2){
        return true;
    }
    else if(n%2==0){
        return false;
    }
    else{
        for(int i=3;i*i<=n;i+=2){
            if(n%i==0){
                return false;
            }
        }
        return true;
    }
}
 
//            < = = = = =    SOLVE    = = = = = >
 
// bool cmp(pair<double,int> x, pair<double,int> y){
//     if(x.first==y.first){
//         return x.second<y.second;
//     }
//     return x.first>y.first;
// }

// void rec(int ){
//     if(){
        
//         return;
//     }

//     return;
// }
 
int solve() {fastio
    string s;
    cin>>s;
    if(s=="ABC")cout<<"ARC";
    else cout<<"ABC";
    return 0;
}

//            < = = = = =    MAIN     = = = = = >
 
int main() {fastio
    
 	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
    
    int t=1;
     // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

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

using namespace std;

struct expand_type {
    template <typename... T>
    expand_type (T&&...) {}
};
template <typename... ArgTypes>
void print (ArgTypes... args) {
    expand_type {0, (cerr << args << ", ", 0)...};
    cerr << "\b\b \n";
}
#define printv(x) cerr << "["; for(auto i : (x)) cerr << i << ", "; cerr << "\b\b]\n";

typedef unsigned long long ull;
typedef long double ld;


void solve () {
    int k;
    cin >> k;
    string s;
    cin >> s;
    int l = (int) s.size();
    if (l <= k) {
        cout << s << endl;
    } else {
        cout << s.substr(0, k) << "..." << endl;
    }
}

int main () {
    std::ios::sync_with_stdio (false);
    cin.tie (nullptr);
    cout.tie (nullptr);
    solve();
    return 0;
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define debug(x) cout << #x << ": " << (x) << endl
using namespace std;

using ull = unsigned long long;
using ll = long long;

using Int = int;
using Double = double;

using P = pair<Int, Int>;
using V = vector<Int>;
using M = vector<V>;

const double PI  = 3.141592653589793238463;
const int MOD = 1000000007;
const Int INF = numeric_limits<Int>::max() / 3;

int min_distance(int h, int w, const vector<vector<bool>>& sss){
    // 番兵で囲む
    vector<vector<bool>> tss(h + 2, vector<bool>(w + 2, false));
    for(int i = 1; i < h + 1; i++){
        for(int j = 1; j < w + 1; j++){
            tss[i][j] = sss[i - 1][j - 1];
        }
    }

    // 距離
    M dss(h + 2, V(w + 2, INF));

    // 距離が確定した場所のフラグ
    vector<vector<bool>> fss(h + 2, vector<bool>(w + 2));
    for(int i = 0; i < h + 2; i++){
        for(int j = 0; j < w + 2; j++){
            fss[i][j] = !tss[i][j];
        }
    }

    // ダイクストラ法の優先度付き待ち行列
    using Node = pair<int, P>; // (距離，(座標x，座標y))
    priority_queue<Node, vector<Node>, greater<Node>> que;

    // ダイクストラ法
    que.push(Node(1, P(1, 1)));
    while(!que.empty()){
        Node node = que.top();
        int d = node.first;
        int x = node.second.first, y = node.second.second;
        que.pop();
        fss[x][y] = true;
        dss[x][y] = d;
        
        int dxs[] = {0, 1, 0, -1};
        int dys[] = {1, 0, -1, 0};
        for(int k = 0; k < 4; k++){
            int x2 = x + dxs[k];
            int y2 = y + dys[k];
            if(tss[x2][y2] && !fss[x2][y2] && dss[x2][y2] > d + 1){
                dss[x2][y2] = d + 1;
                que.push(Node(d + 1, P(x2, y2)));
            }
        }
    }
    
    return dss[h][w];
}

int count_black(int h, int w, const vector<vector<bool>>& sss){
    int b = 0;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(!sss[i][j]){
                b++;
            }
        }
    }
    return b;
}

int solve(int h, int w, const vector<vector<bool>>& sss){
    int d = min_distance(h, w, sss);
    if(d == INF){
        return -1;
    }else{
        return h * w - d - count_black(h, w, sss);
    }
}

int main(int argc, char* argv[]){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int h, w;
    cin >> h >> w;
    
    vector<vector<bool>> sss(h, vector<bool>(w, false));
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            char s;
            cin >> s;
            sss[i][j] = (s == '.');
        }
    }

    cout << solve(h, w, sss) << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n, m, q, mod;
int able[2][1000010];
struct SET {
    int fa[300010];
    inline void init(int n) {
        for (int i = 1; i <= n; i++) fa[i] = i;
    }
    inline int gf(int a) {
        return a == fa[a] ? a : fa[a] = gf(fa[a]);
    }
    inline int merge(int a, int b) {
        fa[gf(a)] = gf(b);
    }
} Set;
vector < pair <int, int> > to[50010];
inline int getHash(int a, int b, int c) {
    return a * 6 - b * 3 - c;
}
int main() {
    scanf("%d%d%d%d", &n, &m, &q, &mod);
    int tmp, g = 0;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        if (i == 1) tmp = w;
        else if (w != tmp) g = __gcd(g, abs(w - tmp));
        to[u].push_back(make_pair(v, w));
        to[v].push_back(make_pair(u, w));
    }
    if (g == 0) g = mod;
    mod = __gcd(3 * g, mod);
    int z = to[1][0].second % g;
    Set.init(6 * n);
    for (int i = 1; i <= n; i++) {
        for (auto node : to[i]) {
            int v = node.first, w = node.second;
            w = (w - z) % mod / g;
            for (int j = 0; j < 3; j++) {
                Set.merge(getHash(v, 0, j), getHash(i, 1, (j * 2 + w) % 3));
                Set.merge(getHash(v, 1, j), getHash(i, 0, (j * 2 + w) % 3));
                Set.merge(getHash(i, 0, j), getHash(v, 1, (j * 2 + w) % 3));
                Set.merge(getHash(i, 1, j), getHash(v, 0, (j * 2 + w) % 3));
            }
        }
    }
    for (int i = 0, j = z; !able[(++i) & 1][j = j * 2 % mod]; ) able[i & 1][j] = 1;
    for (int i = 1; i <= q; i++) {
        int s, t, r, tag = 0;
        scanf("%d%d%d", &s, &t, &r);
        for (int p = 0; p < 2; p++)
            for (int q = 0; q < 3; q++) {
                if (Set.gf(getHash(t, 0, 0)) == Set.gf(getHash(s, p, q))) {
                    if (able[p][(r + z + (3 - q) * g) % mod]) tag = 1;
                }
            }
        puts(tag ? "YES" : "NO");
    }
    return 0;
}

Measured memory_bytes: 12416
import java.util.*;
public class Main{
	public static void main(String args[]){
		Scanner sc =  new Scanner(System.in);
		while(sc.hasNext()){
			int month[] = {31,29,31,30,31,30,31,31,30,31,30,31};
			int in1 = sc.nextInt()-1;
			int day = 0;
			String youbi[] = {"Thursday","Friday","Saturday","Sunday","Monday","Tuesday","Wednesday"};
			for(int i = 0; i<in1; i++){
				day += month[i];
			}
			int in2 = sc.nextInt();
			if(in2 == 0){
				continue;
			}
			day += --in2;
			day %= 7;
			System.out.println(youbi[day]);
		}	
	}
}

Measured memory_bytes: 26316