akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<limits>
#include<deque>
#include<map>
#include<list>
#include<set>
#include <unordered_set>
#include<vector>
#include<cmath>
#include<cstdio>
#include<memory>
#include<bitset>
#include<stack>
#include <functional>
#include <queue>
#include <regex>

using namespace std;

constexpr int MOD = 1000000007;
constexpr int INF = 1050000000;

#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl

#define Tof(x) (x) ? Yes : No
#define TOF(x) (x) ? YES : NO
#define tof(x) (x) ? yes : no

using ll = long long;


/*vectorの要素を全部確認するやつだよ。


for (vector<int>::iterator itr = ans.begin(); itr != ans.end(); ++itr) {
	cout << *itr << " ";
}


*/


/*for文でx,yを上下左右確認するやつだよ。

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


for (int i = 0; i < 4; i++) {
	int ny = y + dy[i];
	int nx = x + dx[i];
}
*/

/*繰り返し二乗法だよ。modもとってくれるよ。n^kをmodで割った余りでやってくれるよ。

ll POW_MOD(ll n, ll k, ll mod) {
	ll r = 1;

	for (; k > 0; k >>= 1) {
		if (k & 1) {
			r = (r * n) % mod;
		}
		n = (n * n) % mod;
	}
	return r;
}


*/

/*2重for文書くのめんどくなった時用だよ。

for (int i = 0; i < h; i++) {
	for (int j = 0; j < w; j++) {

	}
}

*/


int main(void) {
	int n, m; cin >> n >> m;
	ll a[100005];
	ll b, c;

	ll ans = 0;
	map<ll,ll> mp;

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



	for (int i = 0; i < m; i++) {
		cin >> b >> c;
		mp[c] += b;
	}


	for (std::map<ll, ll>::reverse_iterator i = mp.rbegin(); i != mp.rend(); ++i) {
		if (n - (i->second) > 0) {
			ans += (i->first) * (i->second);
			n -= i->second;
		}
		else {
			ans += (n) * (i->first);
			break;
		}
	}


	cout << ans << endl;



	return 0;
}


Measured memory_bytes: 13568
N=int(input())
S=[]
for i in range(N):
    S.append(input())
AC=WA=TLE=RE=0
for i in S:
    if i=="AC":
        AC+=1
    if i=="WA":
        WA+=1
    if i=="TLE":
        TLE+=1
    if i=="RE":
        RE+=1
print("""AC x {}
WA x {}
TLE x {}
RE x {}""".format(AC,WA,TLE,RE))

Measured memory_bytes: 16092
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define input freopen("input.txt", "r", stdin);
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);



#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int main()
{
    ll n, ans=0, sum=0;
    cin>>n;
    ll a[n];
    for(ll i=0; i<n; i++) cin>>a[i];
    for(ll i=n-2; i>=0; i--){
        ll x = a[i];
        sum = (sum + a[i+1]) % mod;
        ll prc = (x * sum) % mod;
        ans = (ans + prc) % mod;
    }
    cout<<ans;
}








Measured memory_bytes: 5160
#include <iostream>
#include <vector>
#include <numeric>
#include <set>
#include <cmath>
using namespace std;
#define ll long long

int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
    
    int n, K;
    cin >> n >> K;
    vector<int> V(n);
    for (int &v : V) cin >> v;
    vector<bool> dp(K + 1);
    
    dp[0] = false;
    for (int i = 1; i <= K; i++){
        bool foundALoseSit = false;
        for (int number : V){
            if (number <= i){
                if (dp[i - number] == 0){
                    foundALoseSit = true;
                    break;
                }
            }
        }
        dp[i] = foundALoseSit;
    }
    if (dp[K]){
        cout << "First";
    } else {
        cout << "Second";
    }
    cout << endl;
}

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

int main() {

    int a,b,c;
    scanf("%d%d%d", &a,&b,&c);

    if((b-a) == (c-b)){
        puts("YES");
    }else{
        puts("NO");
    }
    
    return 0;
    
}


Measured memory_bytes: 128
import sys
input = sys.stdin.readline
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

def solve():
  n,m =(int(i) for i in input().split())
  uf = UnionFind(n)
  for i in range(m):
    x,y,z = (int(i) for i in input().split())
    uf.union(x-1,y-1)
  print(uf.group_count())
solve()

Measured memory_bytes: 62680
sx,sy,tx,ty=map(int,input().split())
print('U'*(ty-sy)+'R'*(tx-sx)+'D'*(ty-sy)+'L'*(tx-sx)+'LU'+'U'*(ty-sy)+'R'*(tx-sx)+'RDRD'+'D'*(ty-sy)+'L'*(tx-sx)+'LU')

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

int main(){
    int n,k;
    cin>>n>>k;
    vector<int>a(n);
    rep(i,n)cin>>a[i];
    for(int i=k; i<n; ++i){
        if(a[i-k]<a[i])cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}

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

typedef long long ll;
typedef vector<ll> vec;

int main() {
    int N;
    cin >> N;
    vec H(N);
    rep(i, N) cin >> H[i];
    
    for (int i=N-1; i>0; i--) {
        if (H[i] < H[i-1]) {
            H[i-1]--;
            if (H[i] < H[i-1]) {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    
    cout << "Yes" << endl;
    
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>

int n, ac, wa, tle, re;
std::string sss;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		std::cin>>sss;
		if(sss == "AC") ++ac;
		if(sss == "WA") ++wa;
		if(sss == "TLE") ++tle;
		if(sss == "RE") ++re;
	}
	printf("AC x %d\n", ac);
	printf("WA x %d\n", wa);
	printf("TLE x %d\n", tle);
	printf("RE x %d\n", re);
	return 0;
}

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

	static int INF = 2 << 27;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int c[] = new int[n];
		int r[] = new int[n];
		int a[] = new int[k];
		int b[] = new int[k];
		for(int i = 0; i < n; i++) {
			c[i] = sc.nextInt();
			r[i] = sc.nextInt();
		}
		for(int i = 0; i < k; i++) {
			a[i] = sc.nextInt()-1;
			b[i] = sc.nextInt()-1;
		}
		int[][] dis = new int[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(i == j) continue;
				dis[i][j] = INF;
			}
		}
		Node[] node = new Node[n];
		for(int i = 0; i < n; i++) {
			node[i] = new Node();
		}
		for(int i = 0; i < k; i++) {
			node[a[i]].edge_to.add(b[i]);
			node[b[i]].edge_to.add(a[i]);
		}
		for(int i = 0; i < n; i++) {
			ArrayDeque<Data> queue = new ArrayDeque<Data>();
			queue.add(new Data(i,0));
			while(!queue.isEmpty()) {
				Data tmp = queue.poll();
				if(tmp.cost > r[i]) break;
				ArrayList<Integer> edge_to = node[tmp.now].edge_to;
				for(int j = 0; j < edge_to.size(); j++) {
					if(dis[i][edge_to.get(j)] <= tmp.cost + 1) continue;
					dis[i][edge_to.get(j)] = tmp.cost + 1;
					queue.add(new Data(edge_to.get(j),tmp.cost+1));
				}
 			}
		}
		for(int i = 0; i < n; i++) {
			node[i].cost = INF;
		}
		PriorityQueue<Data> queue = new PriorityQueue<Data>();
		queue.add(new Data(0,0));
		while(!queue.isEmpty()) {
			Data tmp = queue.poll();
			if(node[tmp.now].cost <= tmp.cost) continue;
			node[tmp.now].cost = tmp.cost;
			node[tmp.now].check = true;
			for(int i = 0; i < n; i++) {
				if(node[i].check) continue;
				if(dis[tmp.now][i] > r[tmp.now]) continue;
				if(node[i].cost <= tmp.cost + c[tmp.now]) continue;
				queue.add(new Data(i,tmp.cost + c[tmp.now]));
			}
		}
		System.out.println(node[n-1].cost);	
	}
	static class Data implements Comparable<Data>{
		int now;
		int cost;
		Data(int a, int b) {
			now  = a;
			cost = b;
		}
		@Override
		public int compareTo(Data o) {
			return this.cost - o.cost;
		}
	}
	static class Node {
		int cost;
		boolean check;
		ArrayList<Integer> edge_to = new ArrayList<Integer>();
	}
}

Measured memory_bytes: 492916
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
int main(int argc, char *argv[])
{
  char row[12];
  int i;
  int max_diff = INT_MIN;
  int min;
  int n = atoi(fgets(row, sizeof(row), stdin));
 
  if (n == 0) {
    printf("err\n");
    exit(1);
  }
 
  min = atoi(fgets(row, sizeof(row), stdin));
  for (i = 1; i < n; i++) {
    int diff;
    int x = atoi(fgets(row, sizeof(row), stdin));
    diff = x - min;
    if (max_diff < diff) {
      max_diff = diff;
    }
    if (x < min) {
      min = x;
    }
  }
 
  printf("%d\n", max_diff);
  return 0;
}

Measured memory_bytes: 528
#include <iostream>
#include <vector>

int main()
{
	int N, K;
	std::cin >> N >> K;

	int price;
	std::vector<int> priceList;
	for (int i = 0; i < N; i++)
	{
		std::cin >> price;
		priceList.emplace_back(price);
	}

    std::sort(priceList.begin(), priceList.end());
  
    price = 0;
	for (int i = 0; i < K; i++)
	{
      price+=priceList[i];
	}

	std::cout << price << std::endl;
}



Measured memory_bytes: 3164
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))

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

    s64 n, k;
    cin >> n >> k;

    vs32 a(n);
    rep (i, n) cin >> a[i];

    s64 tento = 0;
    rep (i, n)
    {
        for (int j = i + 1; j < n; ++j)
        {
            if (a[i] > a[j]) ++tento;
        }
    }

    vs64 c(n);
    rep (i, n)
    {
        rep (j, n)
        {
            if (a[i] < a[j]) ++c[i];
        }
    }

    s64 ans = tento * k % MOD;
    rep (i, n)
    {
        ans = (ans + (c[i] * (k * (k - 1) / 2 % MOD)) % MOD) % MOD;
    }

    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 256
str1 = gets.split
N,K = str1[0].to_i, str1[1].to_i

a = []
for x in 0...20
  a[x] = 0
end

if N-K+1 >= 0
  a[0] = N-K+1
else
  a[0] = 0
end

b = 2
c = 1
for x in 1...20
  if N >= K/c-1 
    a[x] = (K-1)/c-1 - (K-1)/b + 1
  else
    a[x] = N+1 - ((K-1)/b+1)
  end
  if a[x] < 0
    a[x] = 0
  end
  b = b*2
  c = c*2
end

answer = 0.0
d = 1.0

for x in 0...20
  answer += a[x]*d/(N*1.0)
  d = d*0.5
end

puts answer

Measured memory_bytes: 1788
#include<iostream>

#define NUM 20

using namespace std;

int main(){
	
	int d;
	int s = 0;
	int i;
	
	for (;cin >> d;){
		
		for (i = 1; d * i <= 600 - d; i++){
			s += (i * d) * (i * d) * d;
		}
		cout << s << endl;
		s = 0;
	}
	
	return 0;
}


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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define endl '\n'

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

const ll mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// head

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

    int n;
    cin >> n;

    vll a(n + 1, 1);

    for(int i = 2; i <= n; i++) {
        for(int j = i; j <= n; j += i) {
            a[j]++;
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        ans += a[i] * (ll)i;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 81256
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;
 
#define MOD 1000000007
 
int main() {
	ll n;
	cin>>n;
	vector<ll> v;
	v.pb(0);
	rep(i,0,n){
		ll a;
		cin>>a;
		v.pb(a);
	}
	ll mx = 0;
	ll c = 0;
	rep(i,1,v.sz){
		if(v[i-1]>=v[i])c++;
		else c = 0;
		mx = max(mx,c);
	}
	cout << mx << endl;
	return 0;
}

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

using namespace std;

const int N = (int) 1e5;
const long long mod = (long long) 1e9 + 7;
const long long linf = (long long) 1e18;

int n, m;

bool u[N];

long long d1[N];
long long d2[N];

long long dp1[N];
long long dp2[N];

vector< pair<int, int> > g[N];

void dijkstra(int s, long long d[], long long dp[]) {
  for (int i = 0; i < n; i++) {
    d[i] = linf;
  }    
  d[s] = 0;
  dp[s] = 1;
  set< pair<long long, int> > q;
  q.insert(make_pair(d[s], s));
  while (!q.empty()) {
    int v = q.begin()->second; q.erase(q.begin());
    for (auto to: g[v]) {
      if (d[to.first] > d[v] + to.second) {
        q.erase(make_pair(d[to.first], to.first)); 
        q.insert(make_pair(d[to.first] = d[v] + to.second, to.first));
        dp[to.first] = dp[v];
      } else if (d[to.first] == d[v] + to.second) {
        dp[to.first] += dp[v];
        if (dp[to.first] >= mod) {
          dp[to.first] -= mod;
        }
      }
    }
  }  
}

int main() {
  scanf("%d %d", &n, &m);
  int s, t; scanf("%d %d", &s, &t); --s; --t;
  for (int i = 0; i < m; i++) {
    int u, v, d; scanf("%d %d %d", &u, &v, &d); --u; --v;
    g[u].push_back(make_pair(v, d + d));
    g[v].push_back(make_pair(u, d + d));
  }
  dijkstra(s, d1, dp1);
  dijkstra(t, d2, dp2);
  long long ans = dp1[t] * dp2[s] % mod;
  for (int i = 0; i < n; i++) {
    if (d1[i] == d2[i] && d1[i] == d1[t] / 2) {
      ans -= (dp1[i] * dp2[i] % mod) * (dp1[i] * dp2[i] % mod) % mod;
      if (ans < 0) {
        ans += mod;
      }            
    }
  }
  for (int i = 0; i < n; i++) {
    for (auto j: g[i]) {
      if (d1[i] + d2[j.first] + j.second == d1[t] && d1[i] < d1[t] / 2 && d2[j.first] < d2[s] / 2) {
        ans -= (dp1[i] * dp2[j.first] % mod) * (dp1[i] * dp2[j.first] % mod) % mod;
        if (ans < 0) {
          ans += mod;
        }        
      }
    }
  }
  cout << ans;
}


Measured memory_bytes: 17652
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD 1000000007
using namespace std;

void func(int num_ticket,int num_town,int E,int start,int goal){

	int limit,tmp;

	limit = pow(2,num_ticket);

	double dp[limit][num_town+1];

	for(int i = 0; i < limit; i++){
		for(int k = 1; k <= num_town; k++)dp[i][k] = (double)BIG_NUM;
	}

	int distance[num_town+1][num_town+1];

	for(int i = 1; i <= num_town; i++){
		for(int k = 1; k <= num_town; k++)distance[i][k] = BIG_NUM;
	}

	int ticketTable[num_ticket];

	for(int i = 0; i < num_ticket; i++){
		scanf("%d",&ticketTable[i]);
	}

	int from,to,cost;

	for(int i = 0; i < E; i++){
		scanf("%d %d %d",&from,&to,&cost);
		distance[from][to] = cost;
		distance[to][from] = cost;
	}

	dp[0][start] = 0.0;

	int count;

	while(true){
		count = 0;

		for(int state = 0; state < limit;state++){
			for(int town = 1;town <= num_town; town++){
				if(dp[state][town] != (double)BIG_NUM){
					for(int k = 0; k < num_ticket;k++){
						if(state & (1 << k)){
							//Do nothing
						}else{
							for(int a = 1; a <= num_town;a++){
								if(distance[town][a] != BIG_NUM){
									tmp = state + pow(2,k);
									if(dp[tmp][a] > dp[state][town] + (double)distance[town][a]/(double)ticketTable[k]){
										dp[tmp][a] = dp[state][town] + (double)distance[town][a]/(double)ticketTable[k];
										count++;
									}
								}
							}
						}
					}
				}
			}
		}

		if(count == 0)break;
	}

	double minimum = (double)BIG_NUM;

	for(int i = 0; i < limit; i++){
		minimum = min(minimum,dp[i][goal]);
	}

	if(minimum > 1500000000.0){
		printf("Impossible\n");
	}else{
		printf("%.3lf\n",minimum);
	}
}

int main(){

	int num_ticket,num_town,E,start,goal;
	while(true){
		scanf("%d %d %d %d %d",&num_ticket,&num_town,&E,&start,&goal);
		if(num_ticket == 0 && num_town == 0 && E == 0 && start == 0 && goal == 0)break;

		func(num_ticket,num_town,E,start,goal);
	}

	return 0;
}

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

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


// [mint]
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

int main() {
  int x,y;
  cin >> x >> y;
  if ((x+y)%3) {
    cout << 0 << endl;
    return 0;
  }
  int n = (x+y)/3;
  x-=n; y-=n;
  if(x<0 || y<0) {
    cout << 0 << endl;
    return 0;
  }
  combination c(x+y);
  mint ans = c(x+y, x);
  cout << ans.x << endl;
  return 0;
}

Measured memory_bytes: 10624
// https://atcoder.jp/contests/abc148/tasks/abc148_d

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(_i, n) printf("%d%c", a[_i], _i + 1 == n ? '\n' : ' ')
#define DUMP2D(a, n, m) REP(_i, n) REP(_j, m) printf("%d%c", a[_i][_j], _j + 1 == m ? '\n' : ' '); puts("")

const int N_MAX = 200000;

int N;
int a[N_MAX];

void solve() {
  int K = 0;
  REP(i, N) {
    if (a[i] == K + 1) K++;
  }
  if (K == 0) puts("-1");
  else printf("%d\n", N - K);
}

void input() {
  scanf("%d", &N);
  REP(i, N) scanf("%d", a + i);
}

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


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

int p, q;
string s[15], t[15];

int get_val(vector<tuple<int, int, int>> &v, int R, int C, int S){
    int ret = -1;
    for(auto tp: v){
        int x, y, z;
        tie(x, y, z) = tp;
        int tmp = x*R + y*C + z*S;
        if(ret  < 0) ret = tmp;
        else if(ret != tmp) return -1;
    }
    return ret;
}

void solve(){
    vector<tuple<int, int, int>> v;
    vector<int> indent(p, 0);
    vector<vector<int>> cnt(p, vector<int>(3));
    int R = 0, C = 0, S = 0;
    rep(i, p){
        cnt[i][0] = R; cnt[i][1] = C; cnt[i][2] = S;
        for(int j=0; j<(int)s[i].size() && s[i][j] == '.'; ++j) ++indent[i];
        rep(j, s[i].size()){
            if(s[i][j] == '(') ++R;
            if(s[i][j] == ')') --R;
            if(s[i][j] == '{') ++C;
            if(s[i][j] == '}') --C;
            if(s[i][j] == '[') ++S;
            if(s[i][j] == ']') --S;
        }
    }

    auto check = [&](int x, int y, int z){
        rep(i, p)if(x*cnt[i][0] + y*cnt[i][1] + z*cnt[i][2] != indent[i]){
            return false;
        }
        return true;
    };
    For(x, 1, 21)For(y, 1, 21)For(z, 1, 21){
        if(check(x, y, z)) v.push_back(make_tuple(x, y, z));
    }

    int tR = 0, tC = 0, tS = 0;
    rep(i, q){
        printf("%d", get_val(v, tR, tC, tS));
        printf("%c", i==q-1 ? '\n' : ' ');
        rep(j, t[i].size()){
            if(t[i][j] == '(') ++tR;
            if(t[i][j] == ')') --tR;
            if(t[i][j] == '{') ++tC;
            if(t[i][j] == '}') --tC;
            if(t[i][j] == '[') ++tS;
            if(t[i][j] == ']') --tS;
        }
    }
}

int main(){
    while(scanf("%d%d", &p, &q) && p){
        rep(i, p) cin >> s[i];
        rep(i, q) cin >> t[i];
        solve();
    }
}


Measured memory_bytes: 3460
#include <iostream>
using namespace std;
char tbl[] = {
  0x3f, 0x6, 0x5b, 0x4f, 0x66, 0x6d, 0x7d, 0x27, 0x7f, 0x6f,
};
int main()
{
  for(;;){
    int n;
    cin >> n;
    if(n < 0) break;
    int ans = 0;
    for(int i=0; i<n; i++){
      int j;
      cin >> j;
      ans ^= tbl[j];
      for(int k=0; k<7; k++){
        if((ans & (0x40 >> k)) == (0x40 >> k)) cout << 1;
        else cout << 0;
      }
      cout << endl;
      ans = tbl[j];
    }
  }
  return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

int main() {
	long long N, M;
	std::cin >> N >> M;
	std::vector<long long> A(N);
	std::vector<long long> X(200002, 0);
	std::vector<long long> Y(N + 1, 0);
	for (long long i = 0; i < N; i++) {
		std::cin >> A[i];
		X[A[i]]++;
	}
	for (long long i = 200001; i > 0; i--) {
		X[i - 1] += X[i];
	}
	long long l = 0, r = 200001;
	while (r - l > 1) {
		long long x = (r + l) / 2;
		long long sum = 0;
		for (long long i = 0; i < N; i++) {
			sum += X[std::max(x - A[i], 0LL)];
		}
		if (sum < M) {
			r = x;
		}
		else {
			l = x;
		}
	}
	//std::cout << l << std::endl;
	std::sort(A.begin(), A.end(), [](long long a, long long b) {return a > b; });
	for (long long i = 1; i <= N; i++) {
		Y[i] += A[i - 1] + Y[i - 1];
	}
	long long ans = 0L;
	long long j = 0;
	for (long long i = 0; i < N; i++) {
		long long xx = X[std::max(0LL, l - A[i])];
		ans += Y[xx] + A[i] * xx;
		j += xx;
		//std::cout << xx << std::endl;
	}
	ans -= (j - M) * l;
	std::cout << ans << std::endl;
	return 0;
}



Measured memory_bytes: 3456
/*input
7
DDIDDII
*/

#include <iostream>

using namespace std;

int main()
{
	int N;
	string S;

	cin >> N;
	cin >> S;

	int x = 0;
	int max_value = x;

	for(int i=0;i<N;i++){
		if(S[i] == 'I') x++;
		else if(S[i] == 'D') x--;
		max_value = max(max_value, x);
	}

	cout << max_value << endl;
	
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
static const int MAX_H = 100;
static const int MAX_W = 100;
int main()
{
    int h,w;
    int c[MAX_H][MAX_W];
    string s;
    cin>>h>>w;
    //input
    for(int y=0;y<h;y++){
        cin>>s;
        for(int x=0;x<w;x++){
            c[y][x] = (s[x]=='*'?1:0);
        }
    }
    //output
    
    for(int y=0;y<h;y++){
        for(int i=0;i<2;i++){
            for(int x=0;x<w;x++){
                cout<<(c[y][x]==1?"*":".");
            }
        cout<<endl;
        }
    }
    
    return 0;
}

Measured memory_bytes: 256
x1, y1, x2, y2 = map(int, input().split())
v1x = x2 - x1
v1y = y2 - y1

v2x = -v1y
v2y = v1x
v3x = -v2y
v3y = v2x
x3 = x2 + v2x
y3 = y2 + v2y
x4 = x3 + v3x
y4 = y3 + v3y
print(x3, y3, x4, y4)

Measured memory_bytes: 3060
import java.util.Scanner;
class Main
{
    public static void main(String args[])
    {
	Scanner scan=new Scanner(System.in);
	while(true)
	    {
		int n=scan.nextInt();
		if(n==0)break;
		int ans=0;
		double x=Double.MAX_VALUE;
		for(int i=0;i<n;i++)
		    {
			int num=scan.nextInt();
			double h,w;
			h=scan.nextDouble()/100.0;
			w=scan.nextDouble();
			
			if(x>Math.abs(w/(h*h)-22.0))
			    {
				x=Math.abs(w/(h*h)-22.0);
				ans=num;
			    }
		    }
		System.out.println(ans);
	    }
    }
}

Measured memory_bytes: 36792
// #pragma GCC target("avx2")
#pragma GCC optimize("O3", "unroll-loops")

// #include <bits/extc++.h>
// using namespace __gnu_pbds;

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
// template <typename T>
// using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using pii = pair<int, int>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using Prior = priority_queue<T>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back

#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define RANDOM() random_device __rd; \
                 mt19937 __gen = mt19937(__rd()); \
                 uniform_int_distribution<int> __dis(1, 1E8); \
                 auto rnd = bind(__dis, __gen)

const int INF = 1E18;
const int mod = 1E9 + 7;

int32_t main() {
    fastIO();
    
    int k, sz;
    string s;
    cin >> s >> k, sz = s.size();
    
    vector<vector<int>> pl(26);
    for (int i = 0; i < sz; ++i) pl[s[i] - 'a'].eb(i);
    
    set<string> st;
    
    for (int i = 0; i < 26; ++i) {
        for (auto x : pl[i]) {
            for (int len = 1; len <= k and len + x <= sz; ++len) {
                st.insert(s.substr(x, len));
            }
        }
        if (st.size() >= k) break;
    }
    
    int tok = 0;
    for (auto str : st) {
        if (++tok == k) cout << str << "\n";
    }
    
    return 0;
}

Measured memory_bytes: 384
N,K = [int(x) for x in input().split()]
count = [0]*(K+1)
ans = 0
mod = 1000000007
for i in range(K,0,-1):
    kosuu = pow(K//i,N,mod)
    if K // i >= 2:
        for j in range(K//i,1,-1):
            kosuu -= count[j*i]
    ans += i*kosuu
    count[i] = kosuu
print(ans%mod)

Measured memory_bytes: 11172
#include <bits/stdc++.h>
template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}else{return false;}}
template<class T> inline bool chmax(T&a, T b){if(a < b){a = b; return true;}else{return false;}}
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1.0)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    int n;
    cin >> n;
    cout << (1000 - (n% 1000)) % 1000 << endl;
}


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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    string cmd[] = {"lu", "ld", "ru", "rd"};
    vector<int> ans;
    int N;
    while(true){
        int cnt = 0;
        bool aim = true; //false -> [lu, ru]を目指す true -> [ld, rd]を目指す
        bool left = false, right = false;
        cin >> N;
        if(N == 0) break;
        rep(i, N){
            string S; cin >> S;
            if(S[0] == 'l') left = !left;
            else right = !right;

            if(left == aim && right == aim){
                cnt++;
                aim = !aim;
            }
        }
        ans.push_back(cnt);
    }
    rep(i, ans.size()) cout << ans[i] << endl;
    return 0;
}


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

typedef long long ll;
typedef pair<int,int> PII;
#define CINSPEED std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
#define fi first
#define se second
#define pb push_back

ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){ return a * b / gcd(a,b);}


const int N = 100010,M = 1000010;

int cmp(int a,int b)
{
    return a > b;
}
void solved()
{
    int n,k;
    cin >> n >> k;
    vector<ll>h(n,0);
    for(int i = 0;i < n;i++)
    cin >> h[i];

    sort(h.begin(),h.end(),cmp);
    ll cnt = 0;
    for(int i = n - 1;i >= k;i--)
    {
        cnt += h[i];
    }
    cout << cnt;
}

int main()
{
    CINSPEED;

    solved();
#ifdef LOCAL
    system("pause");
#endif
    return 0;
}

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

int main(){
  int n;
  cin >>n;
  string str;
  cin >>str;
  
  int ans=0;
  for(int i=0; i+2<str.size(); i++){
    string check(3,'a');
    for(int j=0; j<=2; j++){
      check.at(j)=str.at(i+j);
    }
    if(check=="ABC") ans++;
  }
  cout << ans<<endl;
}

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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/02/27  Problem: 067_arc_b / Link: https://abc052.contest.atcoder.jp/tasks/arc067_b?lang=en  ----- */
/* ------問題------

東西方向にのびる直線上に、N 個の町があります。 町には、西から順に 1 から N までの番号がついています。 直線上には座標が設定されていて、東に行くほど座標が大きくなります。 町 i の座標は Xi です。
あなたは今、町 1 にいて、これからほかの全ての町を訪れたいです。 移動する手段は次の 2 種類あります。
直線上を歩いて移動する。 東西どちらに歩いても、1 移動する度に疲労度が A 上がります。
好きな場所へテレポートする。 テレポートをすると、移動した距離によらず疲労度が B 上がります。
この 2 種類の移動を繰り返して全ての町を最適に回った時、疲労度の上昇値の合計の最小値がいくつになるか求めてください。

-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */

LL N,A,B;

LL ans = 0LL;

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

	cin >> N>>A>>B;
	VL a(N);
	FOR(i, 0, N) {
		cin >> a[i];
	}
	FOR(i, 0, N - 1) {
		LL val = (a[i + 1] - a[i])*A;
		ans += min(val, B);
	}

	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
  string s;
  vector<string> str;
  while (cin >> s) {
    if (s[s.size() - 1] == '.' || s[s.size() - 1] == ',') s.erase(s.size() - 1);
    if (3 <= s.size() && s.size() <= 6) str.push_back(s);
  }
  for (vector<string>::iterator it = str.begin(); it != str.end(); ++it) {
    if (it == str.end() - 1) cout << *it << endl;
    else cout << *it << ' ';
  }
}

Measured memory_bytes: 1184
#include <stdio.h>

int main(void)
{
int i,b=0;
int n=0,a=0;
int NUM[10000];

scanf("%d",&n);

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

    while(b < n)
    {
    while(NUM[b] % 2 == 0){
    	NUM[b] = NUM[b] / 2;
    	a++;
    }
    b++;
}
printf("%d",a);
    
	return 0;
}


Measured memory_bytes: 256
// Created by proofbycontradiction on 2019-03-06 16:53.
#include <bits/stdc++.h>
#ifndef LOCAL
#define debug(...) 42
#endif
using namespace std;

#define int long long
#define endl '\n'
#define all(x) (x).begin(), (x).end()

using ii = pair<int, int>;
using vb = vector<bool>;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;
using vvii = vector<vii>;

int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n; cin >> n;
  int f[1 << 16] = {};
  int a[16][16];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> a[i][j];
    }
  }
  const int LIMIT = (1 << n);
  for (int mask = 0; mask < LIMIT; mask++) {
    for (int i = 0; i < n; i++) {
      if ((1 << i) & mask) {
        for (int j = i+1; j < n; j++) {
          if ((1 << j) & mask) {
            f[mask] += a[i][j];
          }
        }
      }
    }
  }
  for (int mask = 1; mask < LIMIT; mask++) {
    for (int grp = mask; grp > 0; grp = (grp - 1) & mask) {
      f[mask] = max(f[grp] + f[mask ^ grp], f[mask]);
    }
  }
  cout << f[LIMIT-1] << endl;
#ifdef LOCAL
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
}


Measured memory_bytes: 768
i=62,f[],y,m,s;main(c){for(;s?++f[y*12+*f+"=>?2J13IK<@V&"[--s]]:~scanf("%d,%d,%d",f,&y,&s)?s=s*4+1:++i<180?i%12>1?(y=f[i])?y>m?m=y:1:++c:1:!printf("%d\n%d\n",c,m););}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> P;
int dp[1010][100000];
int main() {
  int N, W;
  cin >> N >> W;
  vector<int> v(N), w(N);
  REP(i, N) cin >> v[i] >> w[i];
  REP(i, N) {
    for (int j = 0; j <= W; j++) {
      if (j < w[i]) {
        dp[i + 1][j] = dp[i][j];
      } else {
        dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);
      }
    }
  }
  printf("%d\n", dp[N][W]);
}


Measured memory_bytes: 7508
#include<iostream>
using namespace std;
int main(){
	long n;
	cin >> n;
	long arr[n];
	for(long i=0;i <n;i++)cin >> arr[i];
	long arr2[n];
	arr2[0] = 0;
	arr2[1] = abs(arr[1]-arr[0]);
	for(long i=2; i<n; i++){
		long a = abs(arr[i] - arr[i-1]) + arr2[i-1];
		long b = abs(arr[i] - arr[i-2]) + arr2[i-2];
		arr2[i] = min(a, b);
	}
	//for(int i=0;i<n;i++)cout << arr2[i] << endl;
	cout << arr2[n-1] << endl;
	return 0;
}


Measured memory_bytes: 1792
import sys
from collections import deque

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N, M = LI()
G = [[] for _ in range(N+1)] # 隣接リスト

for _ in range(M):
    a, b = LI()
    G[a].append(b)
    G[b].append(a)

par = [None] * (N + 1)
# uからの距離
def bfs(u):
    queue = deque([u])
    d = [None] * (N+1)
    
    d[u] = 0
    while queue:
        v = queue.popleft()
        for i in G[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                par[i] = v
                queue.append(i)
    return d

d = bfs(1)
print('Yes')
print(*par[2:], sep='\n')



Measured memory_bytes: 95356
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
using namespace std;

typedef long long ll;
typedef double lf;
typedef long double Lf;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;

#define TRACE(x) cerr << #x << "  " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define _ << " " <<

#define fi first
#define sec second
#define mp make_pair

const int MAXN = 101;

int n, p[MAXN][300];

char s[MAXN];

int main() {
	scanf("%d",&n);
	REP(i, n) {
		scanf("%s",s);
		int m = strlen(s);
		REP(j, m) p[i][s[j]]++;
	}

	string ans = "";
	for (int i = 'a'; i <= 'z'; i++) {
		int mini = (1 << 30);
		REP(j, n) mini = min(mini, p[j][i]);
		REP(j, mini) ans += (char)i;
	}

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

Measured memory_bytes: 256
n = int(input())
a = [0 for i in range(n)]
for i in range(n):
    a[i] = int(input())
if n == 1:
    print(1)
    exit()
a = sorted(a)
a.append(-1)  # 番兵を追加
written = []  # 最終的に描かれる数字の集合
counter = 1
# a[0]と同じ数字が途切れた時点でcounterが奇数なら追加する
for i in range(1, len(a)):  # n > 1の場合
    # print()
    # print("a[i]:{} a[i-1]:{} counter:{}".format(a[i], a[i-1], counter))
    if a[i] == a[i - 1]:
        counter += 1
    else:
        if counter % 2 == 1:
            written.append(a[i - 1])
        counter = 1
    # print("a[i]:{} a[i-1]:{} counter:{}".format(a[i], a[i - 1], counter))
print(len(written))
# print(written)
# print(a)

Measured memory_bytes: 8268
#ifdef DEBUG
#include "redirect.h"
#endif

#include<bits/stdc++.h>
#define N 200050
using namespace std;

map<int,int> mp;
int a[N];

int main(int argc, char *argv[]) {
#ifdef DEBUG
    init(argc, argv);
#endif
    register int n,i;
    long long ans=0;
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);

    for (i=1;i<=n;i++) {
        ans+=mp[i-a[i]];
        mp[i+a[i]]++;
    }
    
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 21564
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define LLINF (1e18)
#define PI (acos(-1))
#define MOD (1000000007)
#define ALL(v) (v).begin(), (v).end()
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

//-------------------------------------

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s, t;
    cin >> s >> t;
    // dp[i][j] := sのi文字目とtのj文字目までを見た時の文字列の最大の長さ
    vector<vector<int>> dp(3010, vector<int>(3010, 0));
    int n = s.size();
    int m = t.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (s[i] == t[j])
            {
                chmax(dp[i + 1][j + 1], dp[i][j] + 1);
            }
            chmax(dp[i + 1][j + 1], dp[i + 1][j]);
            chmax(dp[i + 1][j + 1], dp[i][j + 1]);
        }
    }
    // cout << "---------------------------------------" << endl;
    // for (int i = 0; i <= n; i++)
    // {
    //     for (int j = 0; j <= m; j++)
    //     {
    //         cout << dp[i][j] << ' ';
    //     }
    //     cout << endl;
    // }
    // cout << "---------------------------------------" << endl;

    string ans = "";
    int mx = dp[n][m];
    while (true)
    {
        if (mx == 0)
        {
            break;
        }
        if (dp[n - 1][m] == mx)
        {
            n--;
        }
        else if (dp[n][m - 1] == mx)
        {
            m--;
        }
        else
        {
            ans += s[n - 1];
            m--;
            n--;
            mx--;
        }
    }

    reverse(ALL(ans));
    cout << ans << endl;
}

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

#define MOD 1000000007
#define lli long long int
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=n-1;i>=0;i--)
#define endl "\n"

using namespace std;

void solve(){
    ///start solving
	lli s,w;
	cin >> s >> w;
	if(w >= s){
		cout << "unsafe\n";
	}else{
		cout << "safe\n";
	}
}

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    
solve();//In case of problems without test case

	return 0;
}




Measured memory_bytes: 3628
#include <bits/stdc++.h>
 
using namespace std;
 
#define INPUT_OUTPUT { \
	freopen("input.txt", "r", stdin); \
	freopen("output.txt", "w", stdout); \
}
#define ll long long
#define Pi acos(-1)
 
int main()
{
	//INPUT_OUTPUT;
	int n, i;
	string s, t;
	cin >> n;
	cin >> s;
	int mid = n/2;
	for(i = 0; i < mid; i++) {
		t += s.at(i);
	}
	if(s.substr(mid,n) == t) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
   int A,B,C;
   cin>>A>>B>>C;
   if(A<=B&&B>=C&&A<=C){
       cout<<"Yes"<<endl;
   }else if(A>=C&&A>=B&&B<=C){
       cout<<"Yes"<<endl;
   }else{
       cout<<"No"<<endl;
   }
}

Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <vector>

int main(int argc, char const* argv[])
{
    int h, w;
    std::cin >> h >> w;

    auto vec = std::vector<std::string>(h);
    for(auto &s: vec)
    {
        std::cin >> s;
    }

    auto result = std::vector<std::vector<int>>(h, std::vector<int>(w, 0));

    for(int i=0; i<h; ++i)
    {
        auto str = vec[i];
        for(int j=0; j<w; ++j)
        {
            auto c = str[j];
            if(c == '#')
            {
                bool top = i == 0;
                bool bottom = i == (h - 1);
                bool left = j == 0;
                bool right = j == (w - 1);

                result[i][j] = -99;

                if(!top)
                {
                    result[i - 1][j]++;
                }
                if(!left)
                {
                    result[i][j - 1]++;
                }
                if(!top && !left)
                {
                    result[i - 1][j - 1]++;
                }
                if(!right)
                {
                    result[i][j + 1]++;
                }
                if(!top && !right)
                {
                    result[i - 1][j + 1]++;
                }
                if(!bottom)
                {
                    result[i + 1][j]++;
                }
                if(!left && !bottom)
                {
                    result[i + 1][j - 1]++;
                }
                if(!right && !bottom)
                {
                    result[i + 1][j + 1]++;
                }
            }
        }
        /* std::cout << std::endl; */
    }

    for(auto hv: result)
    {
        for(auto w: hv)
        {
            if(w < 0)
            {
                std::cout << '#';
            }
            else
            {
                std::cout << w;
            }

        }
        std::cout << std::endl;
    }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	char[][] map;
	int h, w;
	char c;
	
	void run() {
		Scanner scan = new Scanner(System.in);
		while (true) {
			h = scan.nextInt();
			w = scan.nextInt();
			if (w == 0 && h == 0) break;
			map = new char[h][];
			int section = 0;
			scan.nextLine();
			for (int i = 0; i < h; i++)
				map[i] = new char[w];
			for (int y = 0; y < h; y++) {
				String str = scan.nextLine();
				for (int x = 0; x < w; x++) {
					map[y][x] = str.charAt(x);
				}
			}
			for (int y = 0; y < h; y++) {
				for (int x = 0; x < w; x++) {
					if (map[y][x] != 'x') {
						c = map[y][x];
						solve(y, x);
						section++;
					}
				}
			}
			System.out.println(section);
		}
	}
	
	void solve(int y, int x) {
		if (y < 0 || x < 0 || y >= h || x >= w || map[y][x] != c) return;
		map[y][x] = 'x';
		solve(y + 1, x);
		solve(y - 1, x);
		solve(y, x + 1);
		solve(y, x - 1);
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 28888
class StronglyConnectedComponents
    def initialize(n)
        @normal=Array.new(n){[]}
        @reverse=Array.new(n){[]}
		@compo=Array.new(n){nil}
		@order=[]
		@used=Array.new(n){false}
    end
	def add(a, b)
		@normal[a] << b
		@reverse[b] << a
	end
	def dfs(i)
		return if @used[i]
		@used[i] = true
		@normal[i].each{|n|
			dfs(n)
		}
		@order<< i
	end
	def rdfs(i, cnt)
		return if @compo[i]
		@compo[i] = cnt
		@reverse[i].each{|n|
			rdfs(n, cnt)
		}
	end
	def build
		@normal.size.times{|i|
			dfs(i)
		}
		@order.reverse!
		group = 0
		@order.each{|o|
			next if @compo[o]
			rdfs(o, group)
			group+=1
		}
		warn @compo.inspect
		r = Array.new(group){[]}
		@compo.size.times{|i|
			r[@compo[i]] << i
		}
		r
	end
end 

N,M=gets.split.map(&:to_i)
scc=StronglyConnectedComponents.new(N)
M.times{
	a,b=gets.split.map(&:to_i)
	scc.add(a,b)
}

r=scc.build
puts r.size
r.each{|x|
	puts [x.size,*x].join(' ')
}


Measured memory_bytes: 160120
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void){
    int a=250000,z=0;
    char s[200100];
    scanf ("%s",s);
    for (int i=0; i<strlen(s); i++){
        if(s[i]=='A' && a>i){
            a=i;
        }
        if (s[i]=='Z' && z<i){
            z=i ;
        }
    }
    printf ("%d\n",z-a+1);
	return 0 ;
}

Measured memory_bytes: 384
n=int(input())
*a,=map(int,input().split())
*b,=map(int,input().split())

capacity=0
for i in range(n):
    capacity+=max(0,b[i]-a[i]-(b[i]-a[i])%2)

for i in range(n):
    if a[i]>b[i]:
        capacity-=(a[i]-b[i])*2

if capacity>=0:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 73932
#include <iostream>
#include <sstream>
#include <algorithm>
#include <functional>
#include <iterator>
#include <numeric>
#include <cstdint>
#include <cmath>
#include <bitset>
#include <string>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>

#define N_TIMES(i, n)     for ( uint64_t i = 0;     i <  n; ++i )
#define N_TIMES_REV(i, n) for (  int64_t i = n - 1; i >= 0; --i )

using namespace std;

int main()
{
  string S;
  cin >> S;

  uint64_t Q;
  cin >> Q;

  uint64_t inv = 0;
  vector<char> head, tail;
  N_TIMES(q, Q) {
    uint64_t cmd;
    cin >> cmd;

    if (cmd == 1) {
      inv = (inv + 1) % 2;
    } else { // cmd == 2
      uint64_t F;
      char C;
      cin >> F >> C;
      --F;
      
      uint64_t D = (inv + F) % 2;
      if (D == 0) {
        head.push_back(C);
      } else { // D == 1
        tail.push_back(C);
      }
    }
  }

  string T = "";
  if (inv == 0) {
    for (auto itr = head.rbegin(); itr != head.rend(); ++itr) { T += *itr; }

    T += S;

    for (auto itr = tail.begin(); itr != tail.end(); ++itr) { T += *itr; }
  } else { // inv == 1
    for (auto itr = tail.rbegin(); itr != tail.rend(); ++itr) { T += *itr; }

    reverse(S.begin(), S.end());
    T += S;

    for (auto itr = head.begin(); itr != head.end(); ++itr) { T += *itr; }
  }
  cout << T << endl;

  return 0;
}

Measured memory_bytes: 1368
import java.util.Arrays;
import java.util.Scanner;

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

    scanner.nextLine();
    final int[] n = Arrays.stream(scanner.nextLine().split(" "))
        .mapToInt(Integer::parseInt)
        .toArray();

    final int x = Arrays.stream(n).sum() / n.length;

    int cost0 = 0;
    int cost1 = 0;
    for (int i = 0; i < n.length; i++) {
      cost0 += (n[i] - x) * (n[i] - x);
      cost1 += (n[i] - (x + 1)) * (n[i] - (x + 1));
    }

    System.out.println(Math.min(cost0, cost1));
  }
}

Measured memory_bytes: 27860