akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const long long INF = (long long)1e18 + 100;

struct Edge
{
	int to;
	long long capacity;
};

struct Dinic
{
	struct Edge_Res
	{
		int to;
		long long capacity;
		int reverse_idx;
		bool is_backword;
	};

	const vector<vector<Edge>> &g_orig;
	int V;
	vector<vector<Edge_Res>> resnet;
	int s, t;
	long long max_flow;
	vector<int> level;
	vector<int> iter;

	Dinic(const vector<vector<Edge>> &g) : g_orig(g), V(g.size()), resnet(V) {
		for (int i = 0; i < V; i++) {
			for (const Edge &e : g[i]) {
				resnet[i].push_back(Edge_Res{e.to, e.capacity, (int)resnet[e.to].size(), false});
				resnet[e.to].push_back(Edge_Res{i, 0, (int)resnet[i].size()-1, true});
			}
		}
	}

	bool is_s(int v) {
		return level[v] >= 0;
	}

	void calc(int s, int t) {
		this->s = s;
		this->t = t;
		max_flow = 0;
		while (true) {
			bfs(s);
			if (level[t] == -1) break;
			iter.assign(V, 0);
			while (true) {
				long long f = dfs(s, INF);
				if (f > 0) max_flow += f;
				else break;
			}
		}
		iter.clear();
		iter.shrink_to_fit();
	}

	void bfs(int s) {
		level.assign(V, -1);
		queue<int> q;
		q.push(s);
		level[s] = 0;
		while (!q.empty()) {
			int v = q.front(); q.pop();
			for (Edge_Res &e : resnet[v]) {
				if (e.capacity <= 0) continue;
				if (level[e.to] != -1) continue;
				level[e.to] = level[v] + 1;
				q.push(e.to);
			}
		}
	}

	long long dfs(int v, long long flow) {
		if (v == t) return flow;
		for (int &i = iter[v]; i < resnet[v].size(); i++) {
			Edge_Res &e = resnet[v][i];
			if (e.capacity <= 0) continue;
			if (level[e.to] <= level[v]) continue;
			long long f = dfs(e.to, min(flow, e.capacity));
			if (f == 0) continue;
			e.capacity -= f;
			resnet[e.to][e.reverse_idx].capacity += f;
			return f;
		}
		return 0;
	}
};

int main() {
	int h, w;
	cin >> h >> w;
	vector<string> a(h);
	for (int i = 0; i < h; i++) {
		cin >> a[i];
	}
	vector<vector<Edge>> g(h + w + 2);
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (a[i][j] == 'S') {
				g[h+w].push_back({i, INF});
				g[h+w].push_back({h+j, INF});
			} else if (a[i][j] == 'T') {
				g[i].push_back({h+w+1, INF});
				g[h+j].push_back({h+w+1, INF});
			} else if (a[i][j] == 'o') {
				g[i].push_back({h+j, 1});
				g[h+j].push_back({i, 1});
			}
		}
	}
	Dinic D(g);
	D.calc(h+w, h+w+1);
	long long ans = D.max_flow;
	if (ans >= INF) ans = -1;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4768
#include <bits/stdc++.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep1(i,n) for (int i = 1; i <= n; ++i)
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline T intceil(T a, T b) { return (a + (b - 1)) / b; }
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
const long long MOD = 1e9+7;
#define precout() cout << std::fixed << std::setprecision(20);
const string alphabet = "abcdefghijklmnopqrstuvwxyz";
const int dy[4] = { 0, 1, 0, -1 };
const int dx[4] = { 1, 0, -1, 0 };
typedef complex<double> cd;
static const double pi = 3.141592653589793;
// if(nextH >= 0 && nextH < H && nextW >= 0 && nextW < W)

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

  int n; cin >> n;

  rep1(i, 3500) {
    rep1(j, 3500) {
      double tmp = 4.0/n - 1.0/i - 1.0/j;
      if(tmp <= 0) continue;
      if((abs((1.0/tmp) - (int)(1.0/tmp)) < 0.00000001)) {
        int k = 1.0/tmp;
        cout << i << " " << j << " " << k << endl;
        return 0;
      }
    }
  }
}


Measured memory_bytes: 256
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a=ii()
if a%2==0:
  b=a//2
  print(b*(a-1))
else:
  b=(a-1)//2
  print(a*b)

Measured memory_bytes: 67916
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <string.h>
#include <ctype.h>

int main(void)
{
  int a,b,c,d;
  scanf("%d %d %d %d",&a,&b,&c,&d);
  printf("%s\n", (( a+b > c+d )? "Left" : ( a+b < c+d )?"Right":"Balanced"));
  return EXIT_SUCCESS; 
}


Measured memory_bytes: 128
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<utility>
#include<vector>

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define per(i, a, n)  for(int i=n-1; i>=a; i--)
#define all(x)  (x).begin(), (x).end()
#define MAX 1e18
using namespace std;
typedef long long ll;

int main(){
  ll H,W;  cin >> H >> W;
  ll sA, sB, sC;
  ll ans = ll(MAX);
  rep(h, 1, H){
    int w = W/2;
    sA = h * W;
    sB = (H-h) * w;
    sC = (H-h)*(W-w);
    ans = min(ans, max({sA, sB, sC}) - min({sA, sB, sC}));
    sB = (H-h)/2 * W;
    sC = (H-h-(H-h)/2) * W;
    ans = min(ans, max({sA, sB, sC}) - min({sA, sB, sC}));
  }
  if(H != W){
    ll tmp = H;
    H = W;
    W = tmp;

    rep(h, 1, H){
      int w = W/2;
      sA = h * W;
      sB = (H-h) * w;
      sC = (H-h)*(W-w);
      ans = min(ans, max({sA, sB, sC}) - min({sA, sB, sC}));
      sB = (H-h)/2 * W;
      sC = (H-h-(H-h)/2) * W;
      ans = min(ans, max({sA, sB, sC}) - min({sA, sB, sC}));
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
a = {}
ANS = 0
for x,y in Counter(A).items():
    if y >= 2: 
        a[x] = [y, (y*(y-1))//2]
        ANS += (y*(y-1))//2
for i in range(n):
    ans = ANS
    if A[i] in a:
        x = a[A[i]][0]-1
        ans -= a[A[i]][1]
        ans += (x*(x-1))//2
    print(ans)

Measured memory_bytes: 34036
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
#include<string>
#include<algorithm>
#define inf 0x3f3f3f3f
#define ll long long
#define ull unsigned long long
#define pi acos(-1.0)
using namespace std;
const int maxn = 1e6+5;
double a[200];

bool cmp(double x, double y){ return x > y; }

int main(){
	int n, m; cin >> n >> m;
	double sum = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		sum += a[i];
	}
	sum /= 4 * m;
	sort(a + 1, a + n + 1, cmp);
	bool ok = 1;
	for(int i = 1; i <= m; i++) if(a[i] < sum) ok = 0;
	if(ok) cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 256
N,*list1 = open(0).read().split()

N=int(N)

#print(N)

list1=[int(i) for i in list1]

list1.sort(reverse=True)

#print(list1)

aaa=[]

bbb=[]


for i,n in enumerate(list1):
    if (i+1)%2 == 1:
        aaa.append(list1[i])
    else:
        bbb.append(list1[i])


#print(aaa)

#print(bbb)

print(sum(aaa)-sum(bbb))

Measured memory_bytes: 9192
def checkWays(n,x)
  count = 0
  catch(:stop) do
    n.downto(1) do |n1|
      (n1-1).downto(1) do |n2|
        n3 = x - n1 - n2
        throw :stop if (n3 >= n1)
        break if (n3 >= n2)
        count += 1 if (n3 > 0)
      end
    end
  end
  puts count
end

while ((n,x = gets.split(" ").map(&:to_i)).inject(:+) != 0) do
  checkWays(n,x)
end

Measured memory_bytes: 8604
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
string S, T;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

mat G(1e+5, vec(0));
vector<bool> used(1e+5, false);
bool ok = false;
ll dfs(int v){
    used[v] = true;
    int odd_num = 0, num = 0;
    for(ll to : G[v]){
        if(!used[to]){
            int temp = dfs(to);
            num += temp;
            odd_num += temp%2;
        }
    }
    if(odd_num >= 2) ok = true;
    return num + 1;
}

int main() {
    cin>>N;
    rep(i,N - 1){
        cin>>A>>B;
        --A;
        --B;
        G[A].push_back(B);
        G[B].push_back(A);
    }
    if(N%2){
        cout<<"First"<<endl;
    }else{
        dfs(0);
        cout<<(ok ? "First" : "Second")<<endl;
    }
}

Measured memory_bytes: 6400
N, K = map(int, input().split())

cnt = []
for i in range(K):
    A = []
    d = int(input())
    A = list(map(int, input().split()))
    for j in range(d):
        if not A[j] in cnt:
            cnt.append(A[j])

ans = 0

for i in range(1, N + 1):
    if not i in cnt:
        ans += 1

print(ans)

Measured memory_bytes: 9200
#include <iostream>

using namespace std;

int main(){
  int n,m,x,y;
  while(true){
    cin >> n;
    if (n == 0)
      break;
    bool jew[21][21];
    for(int i=0;i<441;i++)
      jew[i%21][i/21] = true;
    for(int i=0;i<n;i++){
      cin >> x >> y;
      jew[x][y] = false;
    }
    cin >> m;
    char dir[m];
    int len[m];
    for(int i=0;i<m;i++)
      cin >> dir[i] >> len[i];
    x=10;
    y=10;
    int correct = 0;
    for(int i=0;i<m;i++){
      while(len[i]>0){
	switch(dir[i]){
	case 'N':
	  y++;
	  break;
	case 'E':
	  x++;
	  break;
	case 'S':
	  y--;
	  break;
	case 'W':
	  x--;
	  break;
	}
	if (!jew[x][y]){
	  jew[x][y] = true;
	  n--;
	}
	len[i]--;
      }
    }
    if (n)
      cout << "No" << endl;
    else
      cout << "Yes" << endl;
  }
   
  return 0;
}

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

using namespace std;


bool check(int  s,int t){
    if(s!=t){
        return false;
    }
    return true;
}


int main(){
    string s;
    string t;
    cin >> s;
    cin >> t;
    int a[26];
    int b[26];
    for(int i=0;i<26;i++){
        a[i]=-1;
        b[i]=-1;
    }
    int ans=0;
   
    for(int i=0;i<s.size();i++){
        if(a[s[i]-'a']>=0){//すでに出ているなら対応をみる
            if(check(a[s[i]-'a'],t[i]-'a')){
                
            }
            else{//前回の登場と対応が違うならNo}
                ans++;
                break;
            }
        }
        else{
            a[s[i]-'a']=t[i]-'a';
        }
        if(b[t[i]-'a']>=0){
            if(check(b[t[i]-'a'],s[i]-'a')){
                
            }
            else{
                ans++;
            break;
            }
            
        }
        else{
            b[t[i]-'a']=s[i]-'a';
        }
    }

if(ans>0){
    cout <<"No"<<endl;
}
else{
    cout <<"Yes"<<endl;
}
 return 0;
}

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

int main(){
  int n,q;
  string s;
  cin>>n>>s>>q;
  vector<int>k(q);
  rep(i,q)cin>>k[i];

  rep(query,q){
    int x=k[query];
    ll d=0,m=0,dm=0;
    ll ans=0;
    rep(i,x){
      if(s[i]=='D')d++;
      if(s[i]=='M')m++,dm+=d;
      if(s[i]=='C')ans+=dm;
    }
    for(int i=x; i<n; ++i){
      if(s[i-x]=='D')dm-=m,d--;
      if(s[i-x]=='M')m--;
      if(s[i]=='D')d++;
      if(s[i]=='M')m++,dm+=d;
      if(s[i]=='C')ans+=dm;
    }
    cout<<ans<<endl;
  }
}

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

int main()
{
  string s;
  cin >> s;
  int r = 0;
//  cout << s.size()<< endl;
	for(int i = 0; i < s.size() ; i++)
    {
  	  //cout << s.at(i);
      if(s.at(i)=='1') 
      {
        //cout << s.at(i) << endl ;
        r++;
      }
    }
  cout << r;
}

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

int main(){
  int  n;
  cin>>n;
  if(n%10==3){
    cout<<"bon"<<endl;
  }
  else if(n%10==0||n%10==1||n%10==6||n%10==8){
    cout<<"pon"<<endl;
  }
  else {
    cout<<"hon"<<endl;
  }
}

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

int main()
{
    string x;

    while(1) {
        cin >> x;
        if (x == "0") break;
        int t = 0;
        for (int i = 0; i < x.length(); i++) {
            t += x[i] - '0';
        }
        cout << t << endl;
    }

    return 0;
}

Measured memory_bytes: 3156
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  unordered_map<int,int>m1;
  int flag=0;
  for(int i=0;i<n;i++)
  {
    int m;
    cin>>m;
    if(m1[m]==0)
      m1[m]++;
    else
      flag=1;
  }
  if(flag==1)
    cout<<"NO"<<endl;
  else
    cout<<"YES"<<endl;
  return 0;
}

Measured memory_bytes: 8520
#include <bits/stdc++.h>
using namespace std;
void chmin(int &a, int b) { if (a > b) a = b; }

int N, A, B, C;
vector<int> L;

int rec(int i, int a, int b, int c) {
    if (i==N) {
        if (!a || !b || !c) return 99999999;
        return abs(a-A) + abs(b-B) + abs(c-C);
    }

    int res = rec(i+1, a, b, c);

    chmin(res, rec(i+1, a + L[i], b, c) + (a ? 10 : 0));
    chmin(res, rec(i+1, a, b + L[i], c) + (b ? 10 : 0));
    chmin(res, rec(i+1, a, b, c + L[i]) + (c ? 10 : 0));

    return res;
}

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

    cin >> N >> A >> B >> C;
    L.resize(N); for (int i=0; i<N; i++) cin >> L[i];

    cout << rec(0, 0, 0, 0) << "\n";    

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef long double lb;
#define int long long
#define double long double
typedef pair<int,int> P;
const int MOD = 1000000007;
const ll INF = 1e16;
const double EPS = 1e-10;
const double PI = 3.141592653589793;
template<class T> inline bool chmin(T& a, T b){if(a>b){a = b;return 1;}return 0;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a = b;return 1;}return 0;}
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 


////////////////////////////////////////////////////////////////////


////////////////////////////////////////////////////////////////////
class union_find{
  int N;vector<int> par;
  public:
    union_find(int n){
      N = n;
      par.resize(N);
      rep(i,N)par[i] = -1;
    }
    int find(int x){
      if(par[x] < 0)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;
      par[y] += par[x];
      par[x] = y;
    }
    bool same(int x, int y){
      return find(x) == find(y);
    }
    int size(int x){
      return -par[find(x)];
    }
};

int n,m,k;
vector<int> f[110000], b[110000];
signed main(){
  cin>>n>>m>>k;
  auto u = union_find(n);
  rep(i,m){
    int aa, bb;cin>>aa>>bb;aa--;bb--;
    f[aa].push_back(bb);
    f[bb].push_back(aa);
    u.unite(aa, bb);
  }
  rep(i,k){
    int cc, dd;cin>>cc>>dd;cc--;dd--;
    b[cc].push_back(dd);
    b[dd].push_back(cc);
  }
  vector<int> ans;
  rep(i,n){
    int ret = u.size(i);
    rep(j,f[i].size())if(u.same(i, f[i][j]))ret--;
    rep(j,b[i].size())if(u.same(i, b[i][j]))ret--;
    ans.push_back(ret);
  }
  rep(i,n)cout << ans[i]-1 << (i == n-1 ? "\n" : " ");
}




Measured memory_bytes: 15476
#include<bits/stdc++.h>
#define I64 "%I64d"
#define RAN(v)v.begin(),v.end()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
template<class T>
inline void upd1(T&a,T b){a>b?a=b:0;}
template<class T>
inline void upd2(T&a,T b){a<b?a=b:0;}
struct ano{
	operator ll(){
		ll x=0,y=0,c=getchar();
		while(c<48)
			y=c==45,c=getchar();
		while(c>47)
			x=x*10+c-48,c=getchar();
		return y?-x:x;
	}
}buf;
array<int,26>c;
char t[1000];
int main(){
	int n=buf,m=buf,a=0,b=0;
	for(int i=0;i<n;++i){
		scanf("%s",t);
		for(int j=0;j<m;++j)
			++c[t[j]-97];
	}
	for(int&e:c)
		a+=e/4,b+=e%2;
	if(a<(n&~1)*(m&~1)/4||b>n*m%2)
		puts("No");
	else
		puts("Yes");
}

Measured memory_bytes: 256
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int n;
    scanf("%d",&n);
    
    int i,a,max,min;
    
    long long int sum = 0;
    scanf("%d",&a);
    max = a;
    min = a;
    sum = a+sum;
    for (i = 0; i < n-1; i++)
    {
        scanf("%d",&a);
        if (a < min) {
            min = a;
        }
        if (max < a) {
            max = a;
        }
        sum = sum+a;
    }
    printf("%d %d %lld\n",min,max,sum);
    return 0;

}
    
   

Measured memory_bytes: 600
#include<stdio.h>

int n;

typedef struct node{
  long int key;
  long int parent;
  long int left;
  long int right;
}Node;

int parent(i){
  if(i==1) return -1;
  else return i/2;
}

int left(i){
  if(2*i > n) return -1;
  else return 2*i;
}

int right(i){
  if(2*i+1 > n) return -1;
  else return 2*i+1;
}
	       

int main(){

  int i;
  scanf("%d",&n);

  Node H[n+1];

  for(i=1;i<=n;i++){
    scanf("%d",&H[i]);
    H[i].parent = H[i].left = H[i].right = -1;
  }

  for(i=1;i<=n;i++){
    if(parent(i)!=-1) H[i].parent = H[parent(i)].key;
    if(left(i)!=-1) H[i].left = H[left(i)].key;
    if(right(i)!=-1) H[i].right = H[right(i)].key;
  }

  for(i=1;i<=n;i++){
    printf("node %d: key = %d, ",i,H[i].key);
    if(H[i].parent!=-1) printf("parent key = %d, ",H[i].parent);
    if(H[i].left!=-1) printf("left key = %d, ",H[i].left);
    if(H[i].right!=-1) printf("right key = %d, ",H[i].right);
    printf("\n");
  }
  
  return 0;
}



Measured memory_bytes: 2044
import std.stdio;
import std.algorithm;
import std.math;
import std.conv;
import std.string;

T readNum(T)(){
  return readStr.to!T;
}

T[] readNums(T)(){
  return readStr.split.to!(T[]);
}

string readStr(){
  return readln.chomp;
}

void main(){
	auto n = readNum!int;
	auto p = readNums!int;
	
	int nmin = p[0], ret = 1;
	for(int i = 1; i < n; i++){
		if(p[i] <= nmin){
			nmin = p[i];
			ret++;
		}
	}
	
	writeln(ret);
}

Measured memory_bytes: 10896
#include <cstdio>
#include <iostream>
using namespace std;
long long n;
int f(long long a) {
	int x = 0;
	while (a) {x++;a/=10;}
	return x;
}
int main() {
	cin >> n;
	int MIN = 100;
	for (long long i = 1; i * i <= n; i++) if (n % i == 0 && f(n / i) < MIN) MIN = f(n / i);
	cout << MIN;
	return 0;
}

Measured memory_bytes: 256
use proconio::{input, fastout};
// use std::cmp::max;

#[fastout]
fn main() {
    input! {
        n: usize,
        mut hp: [(i32, i32, i32); n],
    }

    hp.insert(0, (0, 0, 0));
    let mut dp = vec![vec![0;3]; n+1];

    for day in 1..=n {
        dp[day][0] = dp[day-1][1].max(dp[day-1][2]) + hp[day].0;
        dp[day][1] = dp[day-1][0].max(dp[day-1][2]) + hp[day].1;
        dp[day][2] = dp[day-1][0].max(dp[day-1][1]) + hp[day].2;
        // for act in 0..3 {
        //     let oa = (0..3).filter(|&n| n != act).collect::<Vec<usize>>();
        //     dp[day][act] = max(dp[day-1][oa[0]], dp[day-1][oa[1]]) + hp[day][act];
        // }
    }

    println!("{:?}", dp[n].iter().max().unwrap());
}


Measured memory_bytes: 10348
#[allow(dead_code)]
fn main() {
    let s = i::s();
    for i in 1..s.len() {
        if s[i-1] == 'A' && s[i] == 'C' {
            println!("{}", "Yes");
            return;
        }
    }
    println!("{}", "No");
}

#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::*;
#[allow(unused_imports)]
use std::num::*;
#[allow(unused_imports)]
use std::str::*;

#[allow(dead_code)]
mod i {
    use super::*;

    pub fn read<T: FromStr>() -> T {
        stdin()
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>()
            .parse::<T>()
            .ok()
            .unwrap()
    }

    pub fn str() -> String {
        read()
    }

    pub fn s() -> Vec<char> {
        str().chars().collect()
    }

    pub fn i() -> i64 {
        read()
    }

    pub fn u() -> usize {
        read()
    }

    pub fn u2() -> (usize, usize) {
        (read(), read())
    }

    pub fn u3() -> (usize, usize, usize) {
        (read(), read(), read())
    }

    pub fn f() -> f64 {
        read()
    }

    pub fn c() -> char {
        read::<String>().pop().unwrap()
    }

    pub fn iv(n: usize) -> Vec<i64> {
        (0..n).map(|_| i()).collect()
    }

    pub fn iv2(n: usize) -> Vec<(i64, i64)> {
        (0..n).map(|_| iv(2)).map(|a| (a[0], a[1])).collect()
    }

    pub fn uv(n: usize) -> Vec<usize> {
        (0..n).map(|_| u()).collect()
    }

    pub fn uv2(n: usize) -> Vec<(usize, usize)> {
        (0..n).map(|_| uv(2)).map(|a| (a[0], a[1])).collect()
    }

    pub fn uv3(n: usize) -> Vec<(usize, usize, usize)> {
        (0..n).map(|_| uv(3)).map(|a| (a[0], a[1], a[2])).collect()
    }

    pub fn fv(n: usize) -> Vec<f64> {
        (0..n).map(|_| f()).collect()
    }

    pub fn cmap(h: usize) -> Vec<Vec<char>> {
        (0..h).map(|_| s()).collect()
    }
}


Measured memory_bytes: 4352
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("O3")
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<cstdlib>
#include<set>
#include<vector>
#include<sstream>
#include<queue>
#include <iomanip>
#include<unordered_set>
#include <stack>
#include <unordered_map>
#include <map>
#include<numeric>
#include<chrono>
#include <fstream>
constexpr auto INF = 9223372036854775807;
typedef long long int ll;
typedef unsigned long long int ull;
typedef unsigned long int ul;
#define f(i,a,b) for(ll i=(ll)a;i<(ll)b;i+=1)
#define rf(i,a,b) for(ll i=(ll)a;i>=(ll)b;i-=1)
#define endl '\n'
#define N 1000000007 // prime modulo value 
#define M 998244353
#define all(x) x.begin(),x.end()
#define mkp(a,b) make_pair(a,b)
using namespace std;
struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};
inline int mex(unordered_set<int> st)
{
	int m = 0;
	while (st.find(m) != st.end())
	{
		m += 1;
	}
	return m;
}
inline int calculateGrundy(int n)
{
	if (n == 1)
		return 0;
	unordered_set<int> mexi;
	for (int i = 1; i <= sqrt(n); i += 1)
	{
		if (n % i == 0)
		{
			if (n / i != n)
				mexi.insert(calculateGrundy(n / i));
			mexi.insert(calculateGrundy(i));
		}
	}
	return mex(mexi);
}
inline ll gcd(ll a, ll b)
{
	// This is code taken from geeksforgeek
	if (b == 0)
		return a;
	return gcd(b, a % b);
}
/*ll power(ll x, ll y)
{
	// This is code taken from geeksforgeek
	ll res = 1;

	x = x % N;
	if (x == 0) return 0;
	while (y > 0)
	{
		if (y & 1)
			res = (res * x) % N;
		y = y >> 1;
		x = (x * x) % N;
	}
	return res;
}*/
ll power(ll x, ll y)
{
	ll res = 1;

	x = x;

	while (y > 0)
	{

		if (y & 1)
			res = (res * x);

		y = y >> 1;
		x = (x * x);
	}
	return res;
}


/*ll modInverse(ll n, ll p)
{
	return power(n, p - 2, p);
}*/

ll sum(ll n)
{
	return (n * (n + 1)) / 2;
}
ll sum_digit(ll n)
{
	ll ans = 0;
	while (n)
	{
		ans += n % 10;
		n /= 10;
	}
	return ans;
}
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	string s;
	cin>>s;
	if(s=="RRR")
	{
		cout<<3;
	}
	else if(s=="SRS"||s=="RSR"||s=="RSS"||
		s=="SSR")
	{
		cout<<1;
	}
	else if(s=="SSS")
	{
		cout<<0;
	}
	else
	{
		cout<<2;
	}
	
	return 0;
}


Measured memory_bytes: 3640
#pow(a,b,mod)
#np.gcd.outer
#s.count, s.replace, s.index
from math import gcd
from functools import reduce
from itertools import product ##for i in z for j in z -> for i,j in product(z,z)   ||  for i,j in product(z,repeat=2)


n,k=map(int,input().split(' '))
 
mod=10**9+7
 
ar=list(range(1,k+1))
ar.reverse()
 
ans=[0]*(k+1)
for i in ar:
	ava=(k-i)//i+1
	ans[i]=pow(ava,n,mod)-sum(ans[slice(i*2,k+1,i)])
print(sum(i*x for i,x in enumerate(ans))%mod)
	


Measured memory_bytes: 77376
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define DEBUG true
#ifdef ONLINE_JUDGE
#undef DEBUG
#define DEBUG false
#endif 

using namespace std;

#define MAXN ((int)2e5+5)
#define MOD ((int)1e9 + 7)
#define INF ((int)1e9 + 9)
#define ll long long
#define _ << " " <<
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define TRACE(x) if(DEBUG) cerr << #x << " = " << x << endl;
#define TRACE2(x,y) if(DEBUG) cerr << #x << " = " << x << " | " << #y << " = " << y << endl;
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pii pair<int,int>
#define mid ((l+r)/2)

int n,m;
int complete;
map <int,int> mp;

struct Key
{
	int cost;
	int mask;

	bool operator<(Key& rhs)
	{
		return __builtin_popcount(mask) <  __builtin_popcount(rhs.mask); 
	}	
};
vector <Key> key;

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin >> n >> m;
	key.resize(m);
	complete = (1<<n) - 1;
	for (int i = 0; i < m; ++i)
	{
		int b;
		cin >> key[i].cost >> b;
		int ms = 0;
		for (int j = 0; j < b; ++j)
		{
			int box; cin >> box;
			ms |= (1<<(box-1));
		}
		key[i].mask = ms;
	}

	sort(all(key));

	// TRACE2(key.size(), m);

	// for (int i = 0; i < key.size(); ++i)
	// {
	// 	TRACE2(key[i].mask,key[i].cost);
	// }

	for (int i = 0; i < m; ++i)
	{
		for (auto j : mp)
		{
			int newmask = j.first | key[i].mask;
			if(mp.count(newmask))
				mp[newmask] = min(mp[newmask], j.second + key[i].cost);
			else
				mp[newmask] = j.second + key[i].cost; 
		}
		if(mp.count(key[i].mask))
			mp[key[i].mask] = min(mp[key[i].mask], key[i].cost);
		else
			mp[key[i].mask] = key[i].cost;
	}

	if(mp[complete])
		cout << mp[complete] << endl;
	else
		cout << -1 << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for (int i=a; i<b; ++i)

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll N,X,M;
    cin >> N >> X >> M;
    ll cur=X%M, ans=X%M;
    map <ll, ll> pos;
    vector <ll> sums(min(N,M)+2,0);
    sums[1]=cur;
    pos[cur]=1;
    for (int i=2; i<=N; ++i)
    {
        cur = (cur*cur)%M;
        sums[i]=(sums[i-1]+cur);
        if (pos.find(cur)!=pos.end())
        {   
            int prev=pos[cur];
            int len=(i-prev);
            ll rem = N-i+1;
            ans  = ans+ (((rem/len)) * ((sums[i-1]-sums[prev-1])));
            rem = rem%len;
            ans = (ans+ sums[prev+rem-1]-sums[prev-1]);
            break;
        }
        ans=sums[i];
        pos[cur]=i;
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 7144
#include<stdio.h>
#include<string.h>
int main(){
	int n,i,j,f;
	char a[26]={"ABCDEFGHIJKLMNOPQRSTUVWXYZ"};
	char b[26]={"DEFGHIJKLMNOPQRSTUVWXYZABC"};
	char x[1000];
	scanf("%s",x);
		n=strlen(x);
		for(i=0;i<n;i++)
		{
			for(f=0;f<26;f++)
			{
				if(x[i]==b[f])
				{
					printf("%c",a[f]);
				}
			}
		}printf("\n");
	
	
	return 0;
	}


Measured memory_bytes: 2052
from heapq import heappop,heappush
inf = float("inf")

n,m,s = map(int,input().split())

G = [[] for _ in range(n)]
for _ in range(m):
    u,v,cost,time = map(int,input().split())
    u -= 1
    v -= 1
    G[u].append((v,cost,time))
    G[v].append((u,cost,time))

for i in range(n):
    cost,time = map(int,input().split())
    G[i].append((i,-cost,time))

# mint[i][j]
# 銀貨j枚を持って都市iに着くことができる最小時間
mint = [[inf]*2451 for _ in range(n)]

# color[i][j]
# 銀貨j枚を持って都市iに着くことができる最小時間が確定したか
white = 0
black = 1
color = [[white]*2451 for _ in range(n)]

def dijkstra(u,s):
    # 銀貨50枚で49回移動が最大コスト、いらない分は捨てる
    s = min(s,2450)
    mint[u][s] = 0
    color[u][s] = black

    PQ = []
    heappush(PQ,(0,u,s))
    while PQ:
        # minv: PQ内の最小値
        # now: 今いる都市
        # nowcoins: 今持っている銀貨
        minv,now,nowcoins = heappop(PQ)
        color[now][nowcoins] = black
        # 最小時間じゃないなら無視
        if mint[now][nowcoins] < minv: continue
        
        # nxt: 次に行く都市
        # cost: 次の都市に行くのに使う銀貨
        # time: 次の都市に行くのにかかる時間
        # nxtcoins: 次の都市に行った段階で持っている銀貨
        for nxt,cost,time in G[now]:
            nxtcoins = min(nowcoins - cost,2450)
            if nxtcoins < 0: continue
            if color[nxt][nxtcoins]: continue
            if mint[nxt][nxtcoins] > minv + time:
                mint[nxt][nxtcoins] = minv + time
                heappush(PQ,(mint[nxt][nxtcoins],nxt,nxtcoins))

dijkstra(0,s)

# for i in range(n): print(mint[i])
# for i in range(n): print(color[i])
for i in range(1,n): print(min(mint[i]))

Measured memory_bytes: 24944
# -*- coding: utf-8 -*-
v_max = 100010
INF = 1000000100
n, w = map(int, input().split())
weight = [0]*n
value = [0]*n
dp = [[INF for i in range(v_max+1)] for i in range(n+1)]
dp[0][0] = 0

for i in range(n):
    weight[i], value[i] = map(int, input().split())

for i in range(n):
    for j in range(v_max+1):
        if j - value[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j - value[i]] + weight[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

result = 0
for j in range(v_max+1):
    if dp[n][j] <= w:
        result = j
print(result)


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

int main(void) {
	string s; cin >> s;
	string ans = "";
	int i;
	for (i = 0; i < s.size(); i++) {
		if (s[i] == 'B') {
			if (ans != "") { ans.erase(ans.size() - 1); }
		}
		else { ans += s[i]; }
	}

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

Measured memory_bytes: 256
import sys

sys.setrecursionlimit(100000)

while True:
  h, w = map(int, input().split())
  if not h:
    break

  mp = [list("X" + input() + "X") for _ in range(h)]
  mp.insert(0, ["X"] * (w + 2))
  mp.append(["X"] * (w + 2))
  
  direct = ((0, 1), (0, -1), (1, 0), (-1, 0))

  def search(x, y, target):
    mp[y][x] = "X"
    for dx, dy in direct:
      nx, ny = x + dx, y + dy
      if mp[ny][nx] == target:
        search(nx, ny, target)
  
  ans = 0

  for x in range(1, w + 1):
    for y in range(1, h + 1):
      target = mp[y][x]
      if target != "X":
        search(x, y, target)
        ans += 1
  
  print(ans)



Measured memory_bytes: 15900
#include<cstdio>

int main(){
	char word[12];
	char eot[12] = "END_OF_TEXT";
	int i = 1;
	int count = 0;
	char c;
	bool b;

	word[0] = ' ';

	scanf("%c", &c);
	while(c - 10){
		if(96 < c && c < 123){
			word[i] = c - 32;
		}else{
			word[i] = c;
		}
		i++;
		scanf("%c", &c);
	}
	word[i] = ' ';
	i++;

	int j = 0, k = 0;

	c = ' ';
	char t = 'a';

	while(true){
		if(96 < c && c < 123){
			c -= 32;
			b = false;
		}else{
			if(c == '\n'){
				c = ' ';
			}
			b = true;
		}

		if(!(t == c && t == ' ')){
			if(word[j] == c){
				j++;
				if(j == i){
					count++;
					j = 1;
				}
			}else{
				j = 0;
			}

			if(eot[k] == c && b){
				k++;
				if(k == 11 ){
					printf("%d\n", count);
					return 0;
				}
			}else{
				k = 0;
			}
		}
		t = c;
		scanf("%c", &c);
	}
	return 0;
}

Measured memory_bytes: 964
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;
  cin>>n;
  vector<ll>a(3*n),b(2*n);
  rep(i,3*n)cin>>a[i];
  vector<ll> suml(n+1),sumr(n+1);
  rep(i,n)suml[0]+=a[i];
  rep(i,n)sumr[0]+=a[i+2*n];
  ll res=suml[0]-sumr[0];
  multiset<ll>sel;
  rep(i,n)sel.insert(a[i]);



  repi(i,n,2*n)
  {
    ll ni=i-n+1;
    sel.insert(a[i]);

    auto it=sel.begin();
    suml[ni]=suml[ni-1]+a[i]-*it;
    sel.erase(it);
  }
  reverse(all(a));
  multiset<ll,greater<ll>>ser;

  rep(i,n)ser.insert(a[i]);

  repi(i,n,2*n)
  {
    ll ni=i-n+1;
    ser.insert(a[i]);

    auto it=ser.begin();
    sumr[ni]=sumr[ni-1]+a[i]-*it;
    ser.erase(it);
  }
  rep(i,n+1)
  {
    //cout<<suml[i]<<" "<<sumr[n-i]<<endl;
    chmax(res,suml[i]-sumr[n-i]);
  }
  cout<<res<<endl;




  return 0;

}


Measured memory_bytes: 15148
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i = (a);i<=(b);i++)
#define ROF(i,a,b) for(int i = (a);i>=(b);i--)
#define MST(a,x) memset(a,x,sizeof(a))
#define ll long long
#define PB push_back
#define PH push
#define MP make_pair
#define FT first
#define SD second
#define N 800005
#define M 21
#define INF 1000000007
#define MOD 1000000007
#define MOD2 1000000009
#define eps 1e-14
using namespace std;
vector<pair<int,int> >e[N];
map<pair<int,int>,int>mp;
int x[N],y[N],z[N];
int n,m,cnt;
int get(int u,int c)
{
    auto ret = MP(u,c);
    if(mp.find(ret) == mp.end())mp[ret] = ++cnt;
    return mp[ret];
}

int dis[N],vis[N];
queue<int>q;
void spfa(int st)
{
    MST(vis,0);
    FOR(i,1,cnt+n)dis[i] = INF;
    while(!q.empty())q.pop();
    dis[st] = 0;
    vis[st] = 1;
    q.push(st);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(auto v:e[u])
        {
            if(dis[v.FT]>dis[u]+v.SD)
            {
                dis[v.FT] = dis[u]+v.SD;
                if(!vis[v.FT])
                {
                    q.push(v.FT);
                    vis[v.FT] = 1;
                }
            }
        }
    }
}
void addedge(int x,int y,int z)
{
    int xx = get(x,z);
    int yy = get(y,z);
    e[xx].PB(MP(yy,0));
    e[yy].PB(MP(xx,0));
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin>>n>>m)
    {
        FOR(i,1,n)e[i].clear();
        cnt = 0;
        MST(vis,0);
        FOR(i,1,m)
        {
            cin>>x[i]>>y[i]>>z[i];
            addedge(x[i],y[i],z[i]);
        }
        FOR(i,1,m)
        {
            //cout<<get(x[i],z[i])<<" "<<x[i]+cnt<<" "<<get(y[i],z[i])<<" "<<y[i]+cnt<<endl;
            e[get(x[i],z[i])].PB(MP(x[i]+cnt,1));
            e[x[i]+cnt].PB(MP(get(x[i],z[i]),1));
            e[get(y[i],z[i])].PB(MP(y[i]+cnt,1));
            e[y[i]+cnt].PB(MP(get(y[i],z[i]),1));
        }
        spfa(1+cnt);
        if(dis[n+cnt] == INF)cout<<-1<<endl;
        else cout<<dis[n+cnt]/2<<endl;
    }
    return 0;
}


Measured memory_bytes: 71680
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


n = int(readline())
a = list(map(int, readline().split()))
a = a[::-1]
cnt = [0] * n
ans = []
for i in range(n):
    if cnt[n - i - 1] % 2 != a[i]:
        ans.append(n - i)
        memo = make_divisors(n - i)
        for j in range(len(memo)):
            cnt[memo[j] - 1] += 1
print(len(ans))
print(*ans[::-1])


Measured memory_bytes: 67580
#include <stdio.h>

int main(){
    char fig[101];

    while(scanf("%s", fig) != EOF){
        int sum = 0, num, stk, i;
        int nums[1000] = {0};

        for(i = 0; fig[i]; i++)
            switch(fig[i]){
                case 'I' :
                    nums[i] = 1;
                    break;

                case 'V' :
                    nums[i] = 5;
                    break;

                case 'X' :
                    nums[i] = 10;
                    break;

                case 'L' :
                    nums[i] = 50;
                    break;

                case 'C' :
                    nums[i] = 100;
                    break;

                case 'D' :
                    nums[i] = 500;
                    break;

                default :
                    nums[i] = 1000;
            }

        for(i = 0; nums[i]; i++)
            if(nums[i] < nums[i + 1])
                sum -= nums[i];
            else
                sum += nums[i];

        printf("%d\n", sum);
    }

    return 0;
}

Measured memory_bytes: 540
#include<iostream>
#include<cstdio>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	int a=read(),b=read(),c=read();
	puts(a+b>=c?"Yes":"No");
	return 0;
}



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

int main()
{
		int q, i, j, k, a, b;
		string str, opr, opt, tmp;
		cin >> str >> q;

		for (i=0; i<q; i++) {
				cin >> opr;
				if (opr=="print") {
						cin >> a >> b;
						cout << str.substr(a, b-a+1) << "\n";
				} else if (opr=="reverse") {
						cin >> a >> b;
						tmp = str.substr(a, b-a+1);
						k=tmp.size()-1;
						for (j=a; j<=b; j++) { 
								str[j] = tmp[k];
								k--;
						}
				} else if (opr=="replace") {
						cin >> a >> b >> opt;
						k=0;
						for (j=a; j<=b; j++) { 
								str[j] = opt[k];
								k++;
						}
				} else cout << "bad command\n";
		}
}

Measured memory_bytes: 3140
import java.util.*;

class Main{

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long ans = 0;
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                int t = gcd(i,j);
                for(int k = 1;k <= n;k++){
                    ans += gcd(t,k);
                }
            }
        }

        System.out.println(ans);
    }

    static int gcd(int a,int b){
        return b==0? a:gcd(b,a%b);
    }
}

Measured memory_bytes: 35744
import java.util.Scanner;

/**
 * ZAKIREN第5章
 * @author K.Yamauchi
 *
 */
public class Main {

	/**
	 *
	 * @param args
	 */
	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in); // 入力
		int n = Integer.parseInt(scan.nextLine()); // 要素数

		// ソート対象配列の読み込み
		String[] targetArrayStr = scan.nextLine().split(" ");
		int[] targetArray = new int[targetArrayStr.length];
		for (int i = 0; i < targetArrayStr.length; i++) {
			targetArray[i] = Integer.parseInt(targetArrayStr[i]);
		}

		// 読み込み終了
		scan.close();

		for (int k = 0; k < targetArray.length; k++) {
			if (k < targetArray.length - 1) {
				System.out.print(targetArray[k] + " ");
			} else {
				System.out.println(targetArray[k]);
			}
		}

		// ソート呼び出し
		insertionSort(targetArray, n);

	}

	/**
	 * 指定された整数型配列を挿入ソートします。
	 * @param targetArray ソートしたい配列
	 * @param n 要素数
	 * @return 入れ替え回数
	 */
	private static void insertionSort(int[] targetArray, int n) {

		for (int i = 1; i < n; i++) {
			int num = targetArray[i];
			int j = i -1;

			while (j >= 0 && targetArray[j] > num) {
				targetArray[j+1] = targetArray[j];
				j--;
			}
			targetArray[j+1] = num;

			for (int k = 0; k < targetArray.length; k++) {
				if (k < targetArray.length - 1) {
					System.out.print(targetArray[k] + " ");
				} else {
					System.out.println(targetArray[k]);
				}
			}

		}

	}

}



Measured memory_bytes: 30644
import std.stdio;
import std.array;
import std.conv;
import std.algorithm;

struct gom{
	int x = -1;
	int depth=-1;
	this(int a,int b){
		x = a;
		depth = b;
	}
}

gom[][5000] kugi;

void main(){
	string[] fi = readln().split();
	int n = to!int(fi[0]);
	int m = to!int(fi[1]);

	for(int i = 0;i < m;++i){
		string[] input = readln().split();
		int a = to!int(input[0]);
		int b = to!int(input[1]);
		int c = to!int(input[2]);
		kugi[a-1] ~= gom(b-1,c);
	}

	int res = 0;
	int[] now = new int[5001];
	int[] next = new int[5001];
	now[] = -1;
	next[] = -1;
	for(int i = 0;i < n;++i){
		foreach(gom k;kugi[i]){
			now[k.x] = max(now[k.x],k.depth);
		}		
		foreach(int x,int k;now[0..i+1]){
			if(k >= 0){
				++res;
			}
			next[x] = max(next[x],k-1);
			next[x+1] = max(next[x+1],k-1);
		}

		int[] tmp = now;
		now = next;
		next = tmp;
		next[] = -1;
	}

	writeln(res);
}

Measured memory_bytes: 12804
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define all(v) v.begin(), v.end()
#define pb push_back
#define fi first
#define se second
const ll INF = 999999999999999;
const ll MOD = 1000000007;
const ll MAX_N = 500010;
ll A, B, C, D, E, F, G, H, X, Y, Z, P, Q, M, N, T, R, K, W, L, ANS;
string S, S1, S2;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> A >> B >> C >> K;
    if(K) {
        T = min(A, K);
        K -= T;
        ANS += T;
    }
    if(K) {
        T = min(B, K);
        K -= T;
    }
    if(K) {
        T = min(C, K);
        ANS -= T;
    }

    cout << ANS << endl;
}

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

int main(){
#ifdef LOCAL
    freopen("./input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<int> A(n), B(n-1);
    for (int i = 0; i < n-1; i++){
        cin >> B[i];
    }
    
    A[0] = B[0];
    A[n-1] = B[n-2];
    for (int i = 1; i <= n-2; i++){
        A[i] = min(B[i-1], B[i]);
    }
    
    cout << accumulate(A.begin(), A.end(), 0) << "\n";
    
    return 0;
}


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

if 0 in x:
    K -= 1

cand = []
hasleft = x[0] < 0
hasright = x[N-1] > 0
if K == 0:
    cand = [0]
else:
    for i in range(N-K+1):
        left = x[i]
        right = x[i+K-1]
        if left < 0 and right > 0:
            cand.append(min(abs(left)*2+right, right*2+abs(left)))
        elif right < 0:
            cand.append(abs(left))
        elif left > 0:
            cand.append(right)
print(min(cand))

Measured memory_bytes: 14224
#include "bits/stdc++.h"
using namespace std;

struct rect {
	int w;
	int h;
};

int main() {
	while (1) {
		int n, W, D; cin >> n >> W >> D;
		if (!W)break;
		vector<rect>rects;
		rects.push_back(rect{ W,D });
		for (int i = 0; i < n; ++i) {
			int p, s; cin >> p >> s;
			p--;
			rect arect(rects[p]);
			rects.erase(rects.begin() + p);
			s %= 2 * (arect.h + arect.w);
			rect a;
			rect b;
			for (int j = 0; j < 2; ++j) {
				if (s < arect.w) {
					a.h = arect.h; a.w = s;
					b.h = arect.h; b.w = arect.w - s;
					break;
				}
				else {
					s -= arect.w;
					if (s < arect.h) {
						a.h = s; a.w = arect.w;
						b.h = arect.h - s; b.w=arect.w;
						break;
					}
					else {
						s -= arect.h;
					}
				}
			}
			if (a.h*a.w>b.h*b.w) {
				swap(a, b);
			}
			rects.push_back(a);
			rects.push_back(b);
		}
		sort(rects.begin(), rects.end(), [](const rect&l, const rect&r) {return l.h*l.w < r.h*r.w; });
		for (int i = 0; i < rects.size(); ++i) {
			cout << rects[i].h*rects[i].w;
			if (i != rects.size() - 1)cout << " ";
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 3096
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

dp = [[0 for _ in range(w+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j - wv[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j - wv[i][0]] + wv[i][1], dp[i][j])
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j])

print(max(dp[-1]))

Measured memory_bytes: 217964
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

struct edge{
	int to,cap,rev;
	edge(){}
	edge(int tt,int cc,int rr){
		to=tt;
		cap=cc;
		rev=rr;
	}
};

class dinic{
public:
	const int INF=100000;
	vector<edge> G[2001];
	int level[2001];
	int iter[2001];
	void add_edge(int from,int to,int cap){
		G[from].push_back(edge(to,cap,G[to].size()));
		G[to].push_back(edge(from,0,G[from].size()-1));
	}

	void bfs(int s){
		memset(level,-1,sizeof(level));
		queue<int> que;
		level[s]=0;
		que.push(s);
		while(que.size()){
			int v=que.front();
			que.pop();
			for(int i=0;i<G[v].size();i++){
				edge &e=G[v][i];
				if(e.cap>0 && level[e.to]<0){
					level[e.to]=level[v]+1;
					que.push(e.to);
				}
			}
		}
	}

	int dfs(int v,int t,int f){
		if(v==t)return f;
		for(int &i=iter[v];i<G[v].size();i++){
			edge &e=G[v][i];
			if(e.cap>0 && level[v]<level[e.to]){
				int d=dfs(e.to,t,min(e.cap,f));
				if(d>0){
					e.cap-=d;
					G[e.to][e.rev].cap+=d;
					return d;
				}
			}
		}
		return 0;
	}

	int max_flow(int s,int t){
		int flow=0;
		while(1){
			bfs(s);
			if(level[t]<0)return flow;
			memset(iter,0,sizeof(iter));
			int f;
			while((f=dfs(s,t,INF))>0){
				flow+=f;
			}
		}
	}
};

int n,m,s,t;
dinic di;
int a[10001],b[10001];
bool ok[2][2001];

void dfs(int v,int t){
	ok[t][v]=true;
	for(int i=0;i<di.G[v].size();i++){
		edge e=di.G[v][i];
		if(!ok[t][e.to]){
			if((t==1 && e.cap>0)){
				dfs(e.to,t);
			}
			if(t==0 && (v==(n+1) || e.cap==0)){
				dfs(e.to,t);
			}
		}
	}
}

void solve(){
	int S=n,T=n+1;
	for(int i=0;i<=T;i++){
		di.G[i].clear();
	}
	s--;
	t--;
	di.add_edge(S,s,114514);
	di.add_edge(t,T,114514);
	for(int i=0;i<m;i++){
		scanf("%d%d",&a[i],&b[i]);
		a[i]--;
		b[i]--;
		di.add_edge(a[i],b[i],1);
	}
	int val=di.max_flow(S,T);
	memset(ok,false,sizeof(ok));
	dfs(S,1);
	dfs(T,0);
	bool flag=false;
	int cnt=0;
	for(int i=0;i<m;i++){
		if(ok[1][b[i]] && ok[0][a[i]]){
			cnt++;
		}
	}
	if(cnt>0)val++;
	printf("%d %d\n",val,cnt);
}

int main(void){
	while(1){
		scanf("%d%d%d%d",&n,&m,&s,&t);
		if(n==0 && m==0)break;
		solve();
	}
	return 0;
}


Measured memory_bytes: 3724
#include<stdio.h>

int main(){
    int a,x=0, max=0;
    scanf("%d", &a);
    char b[101];
    scanf("%s", b);
    for(int i=0 ; i<=a ; i++){
        if(b[i]=='I')
        x++;
        else
        x--;
        if (max<x){
            max=x;
        }
    }
    printf("%d\n", max);
    return 0;
}

Measured memory_bytes: 1700
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef vector<bool> vb;
 
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,m,n) for(ll i=m;i>=n;i--)
#define all(x) x.begin(),x.end()
#define gll greater<ll>()
 
ll n;
ll l,r;

 
void solve(){
 cin >> n;
 l=0,r=n;
 cout << 0 << endl;
 vector<string> s(n);
  cin >> s[0];
 if(s[0]=="Vacant") {
   return;
 }else { 
  while(1){
   ll m=(l+r)/2;
    cout << m << endl;
    cin >> s[m];
    if(s[m]=="Vacant") break;
    if((m%2&&s[0]!=s[m])||(m%2==0&&s[0]==s[m])) l=m+1;
    else r=m;
  }
 }
}
int main(){
   cin.tie(nullptr);
  ios::sync_with_stdio(false);
  solve();
}  

Measured memory_bytes: 1620
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define REP(i,n) rep(i,0,n)
#define ALL(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;

string str[32]={"101",
				"000000",
				"000011",
				"10010001",
				"010001",
				"000001",
				"100101",
				"10011010",
				"0101",
				"0001",
				"110",
				"01001",
				"10011011",
				"010000",
				"0111",
				"10011000",
				"0110",
				"00100",
				"10011001",
				"10011110",
				"00101",
				"111",
				"10011111",
				"1000",
				"00110",
				"00111",
				"10011100",
				"10011101",
				"000010",
				"10010010",
				"10010011",
				"10010000"};
string bf=" ',-.?";
string af=" .,-'?";

int change_to_10(string s,int from){
	int ans=0;
	rep(i,0,s.size()){
		ans+=(s[i]-'0')*pow(from,s.size()-1-i);
	}
	return ans;
}

signed main(){
	string s;
	while(getline(cin, s)){
		string tmp = "", ans = "";
		rep(i, 0, s.size()){
			if('A' <= s[i] && s[i] <= 'Z'){
				tmp += str[6 + (int)(s[i] - 'A')];
			}else{
				int p = bf.find(s[i]);
				tmp += str[p];
			}
		}
		//cout << tmp <<endl;
		while(tmp.size() % 5 != 0){
			tmp += '0';
		}
		//cout << tmp <<endl;
		rep(i, 0, tmp.size()/ 5){
			int p = change_to_10(tmp.substr(5 * i, 5), 2);
			if(p < 26){
				ans += (char)('A' + p);
			}else{
				ans += af[p - 26];
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1232