akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<numeric>
#include<limits>
#include<bitset>
#include<functional>
#include<type_traits>
#include<queue>
#include<stack>
#include<array>
#include<random>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<string>
#include<ctime>


using namespace std;

using ll = long long int;
using lln = long long unsigned;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const double PI = acos(-1.0);
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define all(v) v.begin(), v.end()
const long MOD = pow(10, 9) + 7;

char alfa[] = { 'A','B' ,'C','D' ,'E' ,'F' ,'G' ,'H' ,'I' ,'J' ,'K' ,'L' ,'M' ,'N' ,'O' ,'P' ,'Q' ,'R' ,'S' ,'T' ,'U' ,'V' ,'W' ,'X' ,'Y','Z' };

inline void finish() {
	cout << -1 << endl;
	exit(0);
}

unsigned GetDigit(double num) {
	return log10(num) + 1;
}

ll modinv(ll a, ll m) {
	ll b = m, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

class Mod {
public:
	static inline ll Add(ll a, ll b) {
		return (a + b) % MOD;
	}

	static inline ll Sub(ll a, ll b) {
		ll ans = (a - b) % MOD;
		return (ans < 0) ? (ans + MOD) : ans;
	}

	static inline ll Mul(ll a, ll b) {
		return (a * b) % MOD;
	}

	static inline ll Div(ll a, ll b) {
		return (a % MOD) * modinv(b, MOD) % MOD;
	}
};



template <typename T>
inline void debug(vector<T> v) {
	cout << "[";
	for (ll i = 0; i < v.size() - 1; ++i) {
		cout << v[i] << ", ";
	}
	cout << v[v.size() - 1] << "]" << endl;
}

void Main();
inline void DebugMain() {
	while (true) {
		Main();
	}
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);

	bool debug = false;
	if (debug) {
		cout << "\x1b[41m" << "Debug Mode " << endl;
	}
	(debug) ? DebugMain() : Main();
	return 0;
}

int parmitation(ll N) {
	ll ans = 1;
	for (ll i = 1; i <= N; i++) {
		ans *= i;
	}

	return ans;
}

int SemiCommonMultiple(ll A, ll ANum, ll B, ll BNum, ll diff, ll max) {
	ll calc;
	calc = diff + B * BNum - A * ANum;

	if (diff + B * BNum > max) {
		return 0;
	}
	else {
		if (calc < 0) {
			SemiCommonMultiple(A, ANum, B, ++BNum, diff, max);
		}
		else if (calc > 0) {
			SemiCommonMultiple(A, ++ANum, B, BNum, diff, max);
		}
		else {
			return A * (ANum + 0.5);
		}
	}
}

inline void Main() {
	ll X, Y, N, M, K;
	vector<bool> A;
	vector<ll> B;
	ll M1 = 1, D1 = 0, M2 = 1, D2 = 0;
	ll ans, temp;
	ll sum = 0, WAcount = 0,ACcount =0, a = 0;
	double avg = 0.0;
	string S;
	string T;
	string Ans = "";
	bool b[8];
	bool flag = false;


	cin >> N >> K;

	for (ll i = 0; i < N; i++) {
		cin >> X;
		B.push_back(X);
	}

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

	for (ll i = 0; i < N - K; i++) {
		sum += B[i];
	}

	cout<<sum;
}



Measured memory_bytes: 2420
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <chrono> //1e+9で割る auto end= chrono::system_clock::now()-st;  cout<<end.count()%1e+9<<endl;
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef long double db;

#define fr first
#define sc second
#define pb push_back
#define rep(i,x) for(ll i=0;i<x;i++)
#define rep1(i,x) for(ll i=1;i<=x;i++)
#define rrep(i,x) for(ll i=x-1;i>=0;i--)
#define rrep1(i,x) for(ll i=x;i>0;i--)
string S,T;
ll imos1[100001],imos2[100001];//ここまでAいくつ

int main()
{
	cin>>S>>T;
	rep(i,S.size()){
		imos1[i]++;
		if(S[i]=='B') imos1[i]++;
		imos1[i+1]+=imos1[i];
		
	}
	rep(i,T.size()){
		imos2[i]++;
		if(T[i]=='B') imos2[i]++;
		imos2[i+1]+=imos2[i];
		//cout<<imos2[i]<<" ";
		//endl;
	}
	//cout<<endl;
	ll Q;
	cin>>Q;
	P p1,p2;
	rep(i,Q){
		ll a,b;
		cin>>p1.fr>>p1.sc;
		cin>>p2.fr>>p2.sc;
		p1.fr--; p2.fr--;
		p1.sc--; p2.sc--;
		a=imos1[p1.sc]-((p1.fr>0)?imos1[p1.fr-1]:0);
		b=imos2[p2.sc]-((p2.fr>0)?imos2[p2.fr-1]:0);
		if((a%3==b%3)) puts("YES");
		else puts("NO");
	}
}

Measured memory_bytes: 2432
#include<iostream>
using namespace std;
int main(){
int a,b,c,d;
d=0;
cin>>a>>b>>c;
if(a>b){
d=a;a=b;b=d;
}
if(b>c){
d=b;b=c;c=d;
}
if(a>b){
d=a;a=b;b=d;
}
cout<<a<<" "<<b<<" "<<c<<endl;
}

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

int main()
{
    string s, t;

    cin >> s >> t;

    if (s == t.substr(0,s.size()) and ((s.size() + 1) == t.size()))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
 
    return 0;
}

Measured memory_bytes: 3620
my $N=<>;
my $s=<>;chomp $s;
my @dat = split(/\s+/, $s);

my $max=1;

my @mrow;

my $sum = -1;

for(my $i=0;$i<=$#dat;$i++){
   $sum++;
   push (@mrow,$max);
   my $a =$dat[$i];
   #print "$i max$max a$a ";
   if($a>0){
      $sum = $sum+ ($a*2)-1;
   }
   $max = $max - $a;
   if($max <0){ print "-1";exit}
   $max = $max *2;
   #print "i$i $sum\n";
}
$sum--;
#print "$sum";

#print "new\n";
$sum = 0;
my $leaf=0;

for(my $i=0;$i<=$#dat;$i++){
   my $a =$dat[$N-$i];
   #print "i$i max$mrow[$N-$i] a$a l$leaf ";
   if($mrow[$N-$i] < ($leaf+$a)  ){
     $leaf = ($mrow[$N-$i]);
     $sum = $sum + $leaf;
   }else{
      $leaf = $a+$leaf;
      $sum = $sum + $leaf;
   }
   #print "i$i $sum\n";
}
print "$sum";

Measured memory_bytes: 19712
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=2e7+1;
int x[N];
int main()
{
	ios::sync_with_stdio(0);
	int a; cin>>a;
	if(a%2==0){
		cout<<-1<<endl;
		return 0;
	}
	int d=7%a;
	int len=0; x[len++]=d;
	while(d&&len<N){
		d=(d*10+7)%a;
		len++;
	}
	if(len==N){
		cout<<-1<<endl;
		return 0;
	}
	cout<<len<<endl;

	return 0;
}


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

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

Measured memory_bytes: 4008
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i32 = int32_t;
using i64 = int64_t;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
//#define fi first
//#define se second
#define debug(x) cout << #x << ": " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1

template <class Cont, class Pred>
Cont filter(const Cont& container, Pred predicate) {
  Cont result;
  copy_if(container.begin(), container.end(), back_inserter(result), predicate);
  return result;
}

// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  unordered_map<string, int> um;

  int N;
  cin >> N;
  int high = 0;
  F0R(i, N) {
    string s;
    cin >> s;
    chmax(high, ++um[s]);
  }

  vector<string> rs;
  for (auto p : um) {
    if (p.second == high) rs.push_back(p.first);
  }
  sort(rng(rs));

  for (auto s : rs) {
    cout << s << newl;
  }
}
#endif


Measured memory_bytes: 26992
a = int(input())
b = int(input())
c = int(input())
x = int(input())

bb = b
cc = c

cnt = 0
 
while a > -1:
    b = bb
    while b > -1:
        c = cc
        while c > -1:
            if (500 * a + 100 * b + 50 * c) == x:
                cnt += 1
            c -= 1
        b -= 1
    a -= 1

print(cnt)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sc.nextInt();
        int a = sc.nextInt() - 1;
        int b = sc.nextInt() - 1;
        int c = sc.nextInt() - 1;
        int d = sc.nextInt() - 1;
        String s = sc.next();
        boolean goaled = false;
        for (;;) {
            if (a == c && b == d) {
                goaled = true;
                break;
            }
            if (a + 1 <= c && a + 1 != b && s.charAt(a + 1) == '.') {
                a++;
            } else if (a + 2 <= c && a + 2 != b && s.charAt(a + 2) == '.') {
                a+=2;
            } else if (b + 1 <= d && (a < b || a == c) && s.charAt(b + 1) == '.') {
                b++;
            } else if (b + 2 <= d && (a < b || a == c) && s.charAt(b + 2) == '.') {
                b+=2;
            } else {
                break;
            }
        }
        System.out.println(goaled ? "Yes" : "No");
    }
}


Measured memory_bytes: 26536
import java.util.Scanner;

public final class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt();
			int[] positions = new int[n];

			int maxPosition = 0;
			for (int i = 0; i < n; i++) {
				int p = scanner.nextInt();
				positions[i] = p;
				if (p > maxPosition) {
					maxPosition = p;
				}
			}

			int minEnergy = Integer.MAX_VALUE;
			for (int p = 0; p <= maxPosition; p++) {
				int energy = 0;
				for (int i = 0; i < positions.length; i++) {
					energy += (int) Math.pow(positions[i] - p, 2);
				}
				if (energy < minEnergy) {
					minEnergy = energy;
				}
			}

			System.out.println(minEnergy);
		}
	}

}


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

int main() {
 int n; cin >> n;
 string s; cin >> s;
 vector<bool> front(26,0),back(26,0);
 int  cnt=0,ans=0;

  for(int i=1;i<n-1;i++){
    for(int j=0;j<i;j++){
       int x=s[j]-'a';
       front[x]=1;
    }
    for(int k=i;k<n;k++){
       int y=s[k]-'a';
       back[y]=1;
    }
    for(int l=0;l<26;l++){
      if(front[l]==1 && back[l]==1)cnt++;
    }
    ans=max(cnt,ans);
    cnt=0;
    for(int l=0;l<26;l++){
      front[l]=0;back[l]=0;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
arr = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = int(input())
print(arr[K - 1])

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

struct Node{
    int left;
    int right;
};

class Tree{
    vector<Node> node;
public:
    Tree(int n){
        node.resize(n);
    }
    int make_tree(vector<int>& pre, int head_p,
                  vector<int>& in , int head_i, int len){
        if (len == 0) return -1;
        int obj = pre[head_p];
        int pos;
        for (pos = head_i; in[pos] != obj; pos++);
        node[obj].left  = make_tree(pre, head_p + 1, in, head_i, pos - head_i);
        node[obj].right = make_tree(pre, head_p + 1 + pos - head_i,
                                    in, pos + 1, head_i + len - 1 - pos);
        return obj;
    }
    void post_order(int p, vector<int>& post){
        if (p == -1) return;
        post_order(node[p].left , post);
        post_order(node[p].right, post);
        post.push_back(p);
    }
};

int main(){
    int n;
    cin >> n;
    vector<int> pre(n);
    vector<int> in(n);
    for (int i = 0; i < n; i++) cin >> pre[i];
    for (int i = 0; i < n; i++) cin >> in[i];
    Tree T(n + 1);
    T.make_tree(pre, 0, in, 0, pre.size());
    vector<int> post;
    T.post_order(pre[0], post);
    for (int i = 0; i < post.size(); i++) {
        cout << post[i] << (i == post.size() - 1 ? '\n' : ' ');
    }
    return 0;
}

Measured memory_bytes: 3172
#include <iostream>
int main()
{
int a,b,c,x,count=0;
std::cin>>a>>b>>c>>x;
for(int i = 0;i<=a;++i)
for(int j = 0;j<=b;++j)
for(int k = 0;k<=c;++k)
if(i*500+j*100+k*50==x){++count;}
std::cout<<count<<std::endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
#define rep(i,n) for (ll i = 0; i < (ll)(n); ++i)
#define rrep(i,j,n) for(ll i = (ll)(j); i < (ll)(n); i++)
#define mrep(i,n) for (ll i = (ll)(n-1); i > 0; i--)
#define be(v) (v).begin(), (v).end()
#define scout cout << fixed << setprecision(20) 
ll INF = 1LL << 60;
ll mod = 1e9 + 7;

int main() {
	int n,a,b; cin >> n >> a >> b;
	string s; cin >> s;
	int k=a+b;
	int A=0;
	int B=0;
	rep(i,n) {
		if(s[i]=='c') cout << "No" << endl;
		else if(s[i]=='a') {
			if(A+B>=k) cout << "No" << endl;
			else {
				cout << "Yes" << endl;
				A++;
			}
		}
		else if(s[i]=='b') {
			if(A+B>=k) cout << "No" << endl;
			else if(b<=B) cout << "No" << endl;
			else {
				cout << "Yes" << endl;
				B++;
			}
		}
	}
}

Measured memory_bytes: 3752
/*
「God Is In His Heaven,
		All's Right With The World.」
*/
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define per(i, a, b) for(int i=(a)-1; i>=(b); i--)
#define each(i, q) for(auto i : q)
#define sz(a) (int)a.size()
#define de(a) cout<<#a<<" = "<<a<<endl
#define dd(a) cout<<#a<<" = "<<a<<" "
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define ffs __builtin_ffs //idxOf(1<-) 
#define clz __builtin_clz //numOf(->0) 
#define ctz __builtin_ctz //numOf(0<-)
#define popcount __builtin_popcount //numOf1
#define parity __builtin_parity //(numOf1)%2
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vpii;
template <typename T> inline void read(T& x) {
	int f = 0, c = getchar(); x = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
	if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T& x, Args& ... args) {
	read(x); read(args...);
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + 48);
}
template <typename T> void writes(T x) { write(x); putchar(' '); }
template <typename T> void writeln(T x) { write(x); puts(""); }
template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, true) : false; }
const int maxn = (int)3e5 + 10;
const ll inf = (ll)1e18;
const int mod = (int)1e9 + 7;
/*
	——ASUKA STRIKES!
*/
ll dp[maxn][20];
string s;
ll dfs(int pos, int x) {
	if (pos == -1)
		return x == 5;
	if (dp[pos][x] != -1)
		return dp[pos][x] % mod;
	ll ans = 0;
	if (s[pos] == '?') {
		rep(i, 0, 10) {
			ans = (ans + dfs(pos - 1, (x * 10 + i) % 13)) % mod;
		}
	}
	else {
		ans = (ans + dfs(pos - 1, (x * 10 + s[pos] - '0') % 13)) % mod;
	}
	dp[pos][x] = ans;
	return ans % mod;
}
int main() {
	cin >> s;
	reverse(all(s));
	memset(dp, -1, sizeof dp);
	printf("%lld\n", dfs(sz(s) - 1, 0));
}


Measured memory_bytes: 55296
#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, x, t;
    cin >> n >> x >> t;
    int ans = (n+x-1)/x*t;
    cout << ans << endl;
    return 0;
}


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

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<double> vd;
typedef vector<vd> vdd;

#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define debug_print(x...) cerr << "line " << __LINE__ << " : "; debug_print_in(x);

template <typename First>
void debug_print_in(First first){
  cerr << first << endl;
  return;
}

template <typename First, typename... Rest>
void debug_print_in(First first, Rest... rest){
  cerr << first << " ";
  debug_print_in(rest...);
  return;
}

void IN(void){
  return;
}

template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
  cin >> first;
  IN(rest...);
  return;
}

template <typename First>
void OUT(First first){
  cout << first << endl;
  return;
}

template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
  cout << first << " ";
  OUT(rest...);
  return;
}

template<class t, class u> void chmax(t&a,u b){if(a<b)a=b;};
template<class t, class u> void chmin(t&a,u b){if(a>b)a=b;};
int popcount(int t){return __builtin_popcount(t);} //GCC
int popcount(ll t){return __builtin_popcountll(t);} //GCC

template <typename T>
void vec_print(vector<T> VEC){
  REP(i, VEC.size()){
    cerr << VEC[i] << " ";
  }
  cerr << endl;
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  REP(i,MAT.size()){
    REP(j,MAT[i].size()){
      cerr << MAT[i][j] << " ";
    }
    cerr << endl;
  }
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  vll A(5);
  REP(i,5) IN(A[i]);
  ll K;
  IN(K);
  sort(ALL(A));
  if(A[4]-A[0]<=K){
    printf("Yay!\n");
  }else{
    printf(":(\n");
  }

  return 0;
}

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


int main(){
	int a, b, c, x;
    int p=0;

    cin >> a >> b >> c >> x;

    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                if(x == i*500+j*100+k*50){
                    p++ ;
                }
            }
        }
    }

    cout << p << endl;

	return 0;
}


Measured memory_bytes: 256
# A - A?C
# ABC ARC の二つのコンテストが開催される
# ABC → ARC → ABC → ARC → ... と 毎週開催される

# 文字列 S の入力
S = input()
# print(S)

if S == 'ABC':
    # print('ARC')
    answer = 'ARC'
elif S == 'ARC':
    # print('ABC')
    answer = 'ABC'

# 結果の出力
print(answer)


Measured memory_bytes: 9020
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(x,y) (x=min(x,y))
#define chmax(x,y) (x=max(x,y))
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}
#define N 200010
int cnt[N], d[2*N];

int main(){
	int n, m;
	cin>>n>>m;
	vector<int> v(n);
	rep(i, n) cin>>v[i];
	rep(i, n) cnt[v[i]]++;
	rep(i, n){
		rep(j, cnt[i+1]) d[N+i+1-j]++;
	}
	int res = 0;
	rep(i, n) if(!d[N+i+1]) res++;
	rep(i, m){
		int x, y;
		cin>>x>>y; x--;
		int &z = v[x];
		if(d[N+z-cnt[z]+1]==1 && N+z-cnt[z]+1>=N+1) res++;
		d[N+z-cnt[z]--+1]--;
		if(d[N+y-cnt[y]]==0 && N+y-cnt[y]>=N+1) res--;
		d[N+y-cnt[y]++]++;
		//if(d[N+z-cnt[z]--+1]-->1) res--;
		//if(d[N+y-cnt[y]++]++>0) res++;
		swap(z, y);
		cout<<res<<endl;
		/*cerr<<"debug"<<endl;
		rep(j, n) cerr<<cnt[j+1]<<endl;
		cerr<<"debug2"<<endl;
		rep(j, n) cerr<<d[N+j+1]<<endl;*/
	}
	return 0;
}


Measured memory_bytes: 3840
using System;

namespace AtCoderABC131D
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            int[][] W = new int[N][];

            for (int i = 0; i < N; i++)
            {
                W[i] = new int[2];
                string[] s = Console.ReadLine().Split(' ');
                W[i][0] = int.Parse(s[0]);
                W[i][1] = int.Parse(s[1]);
            }

            OrgComparer comp = new OrgComparer();
            Array.Sort(W, comp);

            int total = 0;

            for (int i = 0; i < N; i++)
            {
                total += W[i][0];

                if(total > W[i][1])
                {
                    Console.WriteLine("No");
                    return;
                }
            }

            Console.WriteLine("Yes");
        }
    }

    public class OrgComparer : System.Collections.IComparer
    {
        //配列２項目目で昇順
        public int Compare(object x, object y)
        {
            int[] X = (int[])x;
            int[] Y = (int[])y;

            if (X[1] < Y[1])
                return -1;
            if (X[1] > Y[1])
                return 1;

            return 0;
        }
    }

}


Measured memory_bytes: 26404
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<functional>
#include<numeric>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#include<bitset>
#include<random>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0LL,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,n) RFOR(i,0LL,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define COUNT(a,y,x) upper_bound(all(a), y) - lower_bound(all(a), x)
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())
#define pb push_back
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
const ll inf = 1LL << 61;
const ll mod = 1000000007LL;
//const ll mod = 998244353LL;

ll n = 0, m = 0, ans = 0, tmp = 0, ma = -inf, mi = inf;
string s;
bool ok;
ll dx[9] = { 0,1,0,-1,0,1,1,-1,-1 }, dy[9] = { 0,0,1,0,-1,1,-1,1,-1 };
#define endl '\n'
#pragma endregion
#define MAX 222222






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



  cin >> n >> m;
  cin >> s;
  tmp = s[m - 1] - 'A';
  char c = 'a' + tmp;
  s[m - 1] = c;
  cout << s << endl;





  return 0;
}


Measured memory_bytes: 256
using System;


namespace ConsoleApplication9
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] alpha = new int[26];
            while (true)
            {
                    string str = Console.ReadLine();
                if(str == null||str.Length == 0)
                    break;
                else
                {
                    char[] ca = str.ToCharArray();
                    for (int i = 0; i < ca.Length; i++)
                    {
                        if (char.IsUpper(ca[i]))
                            alpha[(int)ca[i] - 65] += 1;
                        else if (char.IsLower(ca[i]))
                            alpha[(int)ca[i] - 97] += 1;
                    }
                }
            }
            for(int i =0;i<alpha.Length;i++)
            {
                Console.WriteLine("{0} : {1}", (char)(i + 97), alpha[i]);
            }
        }
    }
}

Measured memory_bytes: 9236
#include<stdio.h>

int main(){
    int A, B, C, X, Y, N;
    int sumA, sumB, sumAB, sumT;
    int i, j, k;
    int ans = 2000000000;

    scanf("%d %d %d %d %d", &A, &B, &C, &X, &Y);
    if(X<Y){
        N = Y;
    }else{
        N = X;
    }

    for(i=0; i<=N; i++){
        if(X-i>=0){
            sumA = A*(X-i);
        }else{
            sumA = 0;
        }
        if(Y-i>=0){
            sumB = B*(Y-i);
        }else{
            sumB = 0;
        }
        sumAB = C*i*2;
        sumT = sumA + sumB+sumAB;
        if(sumT < ans){
            ans = sumT;            
        }
        //printf("%d\n", sumT);
    }

    printf("%d", ans);

    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi M_PI
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int x[10][10];

int calc(VI a){
    int res = 0;
    REP(i,4) res = x[res][a[i]];
    return res;
}

int check(VI a){
    int res = 0;
    REP(i,5) res = x[res][a[i]];
    return res;
}

int main() {
    REP(i,10) REP(j,10) cin >> x[i][j];
    int ans = 0;
    REP(i,10000){
        VI a(5);
        int d = i;
        REP(j,4){
            a[3-j] = d % 10;
            d /= 10;
        }
        a[4] = calc(a);
        bool f = 0;
        REP(j,5) REP(p,10){
            VI b(a);
            b[j] = p;
            if (b != a){
                if (check(b) == 0) f = 1;
            }
        }
        REP(j,4){
            VI b(a);
            if (b[j] == b[j+1]) continue;
            swap(b[j], b[j+1]);
            if (check(b) == 0) f = 1;
        }
        if (f) ans++;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3180
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();

int main() {
    int n;
    cin >> n;
    vector<int> arr(n, 0);
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    int M = *max_element(arr.begin(), arr.end());
    int m = *min_element(arr.begin(), arr.end());
    cout << M - m << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

typedef long long int ll;
ll n,ans=0;

int dfs(ll a,ll n3,ll n5,ll n7){
    if(a>n)return ans;
    if(n3+n5+n7==3)ans++;
    dfs(a*10+3,1,n5,n7);
    dfs(a*10+5,n3,1,n7);
    dfs(a*10+7,n3,n5,1);
}

int main(){
    scanf("%lld",&n);
    printf("%lld\n",dfs(0,0,0,0));
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#include<math.h>
#include<string.h>
#include<vector>
using namespace std;
#define MAX 200005
#define MOD 998244353
int A[MAX];
int main()
{
    FILE *input=stdin;
    //input=fopen("in.txt","r");
    int t,T=1;
    //fscanf(input,"%d",&T);
    for(t=1; t<=T; t++)
    {
        int K,N,i,j;
        fscanf(input,"%d %d",&K,&N);
        for(i=0;i<N;i++)
        {
            fscanf(input,"%d",&A[i]);
        }
        int res=0;
        for(i=0;i<N;i++)
        {
            res=max(res,(A[(i+1)%N]-A[i]+K)%K);
        }
        res=K-res;
        printf("%d",res);
        if(t!=T) printf("\n");
    }
    fclose(input);
    return 0;
}


Measured memory_bytes: 1024
import java.util.*;
import java.io.*;
public class Main
{
    public static void main(String args[])throws Exception
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw=new PrintWriter(System.out);
        String str[]=br.readLine().split(" ");
        int n=Integer.parseInt(str[0]);
        int k=Integer.parseInt(str[1]);
        int arr[]=new int[n+1];
        for(int i=0;i<k;i++)
        {
            int s=Integer.parseInt(br.readLine());
            str=br.readLine().split(" ");
            for(int j=0;j<s;j++)
            arr[Integer.parseInt(str[j])]++;
        }
        int cntr=0;
        for(int i=1;i<=n;i++)
        if(arr[i]==0)
        cntr++;
        pw.println(cntr);
        pw.flush();
        pw.close();
    }
}

Measured memory_bytes: 33796
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define fl float
#define db double
#define ii pair<ll,ll>
#define pii pair<ii,ii>
#define ford(i,a,b) for(int i=a;i<=b;i++)
#define foru(i,a,b) for(int i=a;i>=b;i--)
#define forv(i,a,b) for(int i=a;i<b;i++)
#define oo 10000000000001
#define ooo -1000000000001
int const maxn=101;
int sum[maxn],n,l,x,ans=0;
int main()
{
    cin>>n>>l;
    sum[0]=0;
    for(int i=1;i<=n;i++){
         cin>>x;
         if(i==1) sum[i]=x;
         else sum[i]=sum[i-1]+x;
    }
    for(int i=0;i<=n;i++){
        if(sum[i]<=l) ans++;
        else break;
    }
    cout<<ans;
    return 0;
}


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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

typedef long long ll;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

#define MAX 100010
int N,M;
int p[MAX];

int par[MAX];
int find(int x) {
  if( x == par[x] ) return x;
  return par[x] = find(par[x]);
}
void unite(int x,int y) {
  x = find(x), y = find(y);
  if( x != y ) par[x] = y;
}

int main() {
  cin >> N >> M;
  map<int,int> mp;
  rep(i,N) {
    cin >> p[i]; --p[i];
    mp[p[i]] = i;
  }
  rep(i,N) par[i] = i;
  int x,y;
  set<int> S;
  rep(i,M) {
    cin >> x >> y;
    --x, --y;
    unite(x,y);
    S.insert(x);
    S.insert(y);
  }
  int cnt = 0;
  rep(i,N) if( !S.count(i) && i == p[i] ) ++cnt;
  rep(i,N) {
    if( !S.count(i) ) continue;
    if( find(i) == find(mp[i]) ) ++cnt;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 13480
x,y=map(int,input().split())
if 0<=x<y or x<y<=0:
    print(y-x)
elif 0<y<x or y<x<0:
    print(2+x-y)
elif x<0<y or y<0<x:
    print(1+abs(x+y))

if x==0 and y<0 :
    print(abs(y)+1)
if y==0 and x>0:
    print(x+1)

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

int main(){
	int h,w,n;
	cin>>h>>w>>n;
	
	int a[n+1],b[h][w],k=1;
	for(int i=1;i<=n;i++)
		cin>>a[i];
		
	for(int i=0;i<h;i++){
		if(i&1)
			for(int j=0;j<w;j++){
				if(a[k]){
					b[i][j]=k;
					a[k]--;
				}
				else{
					while(a[k]==0)
						k++;
					b[i][j]=k;
                                        a[k]--;

				}
			}
		else	
			for(int j=w-1;j>=0;j--){
				if(a[k]){
                                        b[i][j]=k;
                                        a[k]--;
				}
                                else{
                                        while(a[k]==0)
                                                k++;
                                        b[i][j]=k;
                                        a[k]--;

                                }
			}
	}
	
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cout<<b[i][j]<<" ";
		}
		cout<<"\n";
	}
}	


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

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

    //dp[i][j] := 上からi桁まで見て、j(過剰に支払っているかどうか)のときの最小枚数
    vector<vector<int64_t>> dp(N.size() + 1, vector<int64_t>(2, INT_MAX));
    dp[0][0] = 0;
    dp[0][1] = 1;
    for (int64_t i = 0; i < N.size(); i++) {
        //i桁目に対して可能な行動
        //(1)N[i] + 1枚払う
        dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + N[i] - '0' + 1);

        //(2)N[i]枚払う
        dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + N[i] - '0');

        //(3)払わない[一つ上の桁で過剰に払っていた場合のみ可能]
        dp[i + 1][0] = min(dp[i + 1][0], dp[i][1] + 10 - (N[i] - '0'));
        dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] +  9 - (N[i] - '0'));
    }

    cout << dp[N.size()][0] << endl;
}

Measured memory_bytes: 55940
def main():
    x , y = map(int,input().split())
    var2=x
    var4=0
    for loop in range(x+1):
        roger = (2*var2) + (4*var4)
        if roger == y:
            return "Yes"
        var2-=1
        var4+=1
    return "No"
print(main())


Measured memory_bytes: 9108
#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <algorithm>
    #include <queue>
    #include <vector>
    #include <stack>
    #include <map>
    #include <set>
    #include <cmath>
    #include <cctype>
    #include <ctime>
    #include <cassert>
     
    using namespace std;
     
    #define REP(i, n) for (int i = 0; i < (n); ++i)
    #define eps 1e-9
     
    typedef long long ll;
    typedef pair<int, int> pii;
     
    const int INF = 0x7fffffff;
    const int maxn = 1e5 + 10;
    int a[maxn];
    int n;
     
    ll cal() {
        ll t = a[0], ans = 0;
        for (int i = 1; i < n; ++i) {
            if (t < 0) {
                t += a[i];
                if (t <= 0) { ans += 1 - t; t = 1; } continue;
            }
            t += a[i];
            if (t >= 0) { ans += t + 1; t = -1; }
        }
        return ans;
    }
     
    int main() {

        scanf("%d", &n);
        REP(i, n) { scanf("%d", &a[i]); }
        ll ans1 = 0, ans2 = 0, ans3 = 0, ans = 0; int t = a[0];
        if (t == 0) {
            a[0] = 1; ans1 = cal();
            a[0] = -1; ans2 = cal();
            ans = min(ans1, ans2) + 1;
        } else {
            ans1 = cal();
            a[0] = 1;  ans2 = cal() + abs(1 - t);
            a[0] = -1; ans3 = cal() + abs(-1 - t);
            ans = min(ans1, min(ans2, ans3));
        }
        printf("%lld\n", ans);
        return 0;
    }


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

using namespace std;

typedef long long ll;

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 (a>b) { a=b; return 1; } return 0; }
const ll LINF = 1e18;
const ll mod = 1e9 + 7;

ll dp[1010][1010] = {};

template<class T>
void add(T &a, const T b) {
  a += b;
  if (a >= mod) a -= mod;
}

int main()
{
  int h, w; cin >> h >> w;

  vector<string> a(h);
  for (int h_i = 0; h_i < h; ++h_i) {
    cin >> a[h_i];
  }

  dp[0][0] = 1;

  for (int h_i = 0; h_i < h; ++h_i) {
    for (int w_i = 0; w_i < w; ++w_i) {
      if (w_i+1 < w and a[h_i][w_i+1] == '.') add(dp[h_i][w_i+1], dp[h_i][w_i]);
      if (h_i+1 < h and a[h_i+1][w_i] == '.') add(dp[h_i+1][w_i], dp[h_i][w_i]);
    }
  }

  cout << dp[h-1][w-1] << endl;
}

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


int main(){

	int a, b;

	while(cin >> a >> b){

		long m = ( a>=b ? a : b );
		long n = ( a>=b ? b : a );

		while( n != 0 ){
			int temp = n;
			n = m % n;
			m = temp;
		}

		cout << m << " " << a / m * b  << endl;

	}

	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("unroll-loops, no-stack-protector")
#pragma GCC target ("avx")
#pragma GCC target ("avx2")
#pragma GCC target ("fma")
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pci pair <char, int>
#define pld pair <ld, ld>
#define ppld pair <pld, pld>
#define ppll pair <pll, pll>
#define pldl pair <ld, ll>
#define vll vector <ll>
#define vvll vector <vll>
#define vpll vector <pll>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define mll map <ll, ll>
#define fastmap gp_hash_table
#define cd complex <double>
#define vcd vector <cd>
#define PI 3.14159265358979
#define ordered_set tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update>
#pragma 03
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int main(){
	fastio;
	ll d, t, s; cin >> d >> t >> s;
	if (d > t * s) cout << "No\n";
	else cout << "Yes\n";
}

Measured memory_bytes: 3636
#b
import math

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

result = 0
mod_res = 10
for x in [a, b, c, d, e]:
    if 0 < x % 10 < mod_res:
        mod_res = x % 10
flag = True
for x in [a, b, c, d, e]:
    if x % 10 == mod_res and flag:
        result += x
        flag = False
    else:
        result += math.ceil(x / 10) * 10
        
print(result)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n)  for(int i = 0; i < n; i++)
int main(void) {
  int n;
  cin >> n;
  vector<int> data(n);
  rep(i,n) {
    cin >> data.at(i);
  }
  sort(data.begin(),data.end());
  reverse(data.begin(),data.end());
  int ahead = 101;
  int ans = 0;
  rep(i,n){
    if(data.at(i) < ahead){
      ahead = data.at(i);
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
a.sort()
can = []
for i in range(n):
  now = a[i]
  try:
    if now == can[-1][0]:
      can[-1][1] += 1
    else:
      can.append([now,1])
  except:
    #i==0
    can.append([now,1])
l = len(can)
ans = 0
for j in range(l):
  if can[j][1] >= can[j][0]:
    ans += can[j][1] - can[j][0]
  else:
    ans += can[j][1]
#print(can)
print(ans)

Measured memory_bytes: 16760
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
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 ll;
using namespace std;
int main(void){
    int a,b,t;cin>>a>>b>>t;
    int res=t/a*b;
    cout<<res<<endl;
}

Measured memory_bytes: 256
def a_where_is_snuke(H, W, S):
    for r, row in enumerate(S):
        for c, col in enumerate(row):
            if col == 'snuke':
                ans = str(chr(ord('A') + c)) + str(r + 1)
                break
        else:
            continue
        break
    return ans

H, W = [int(i) for i in input().split()]
S = [input().strip().split() for _ in range(H)]
print(a_where_is_snuke(H, W, S))

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

string n;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin>>n;
	for(int i=0;i<3;i++){
		if(n[i]=='9')
			n[i]='1';
		else if(n[i]=='1')
			n[i]='9';
	}

	cout<<n;
	return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from copy import *

n = int(input())
a = list(map(int, input().split()))+[-1]
k = []
t = 1
for i in range(n):
    if a[i] == a[i+1]:
        t += 1
    else:
        if t > 1:
            k.append(t)
            t = 1
ans = 0
for x in k:
    ans += x//2
print(ans)


Measured memory_bytes: 3444
t = int(input())

for _ in range(t):
  n, a, b, c, d = map(int, input().split())
  
  memo = {}
  def f(n):
    if n == 0:
      return 0
    if n == 1:
      return d
    if n in memo:
      return memo[n]

    m2 = n % 2
    m3 = n % 3
    m5 = n % 5 
    ret = min(
      d * n,
      d * m2 + a + f((n - m2) // 2),
      d * m2 + a + f((n + m2) // 2),
      d * m3 + b + f((n - m3) // 3),
      d * (3 - m3) + b + f((n + 3 - m3) // 3),
      d * m5 + c + f((n - m5) // 5),
      d * (5 - m5) + c + f((n + 5 - m5) // 5),
    )
    memo[n] = ret
    return ret
  print(f(n))

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define show(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define show(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
template<typename T> using vec=std::vector<T>;

const int inf=1<<30;
const long long int infll=1LL<<62;
const double eps=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

int prim(const vector<vector<pair<int,int>>> &graph){
    typedef pair<int,int> pii; //(cost,to)
    int res=0;
    priority_queue<pii,vector<pii>,greater<pii>> que;
    vector<bool> used(graph.size());
    que.push(make_pair(0,0));
    while(!que.empty()){
        auto cost=que.top().first;
        auto v=que.top().second;
        que.pop();
        if(used[v]) continue;
        res+=cost;
        used[v]=true;
        for(auto &e:graph[v]){
            if(used[e.second]) continue;
            que.push(e);
        }
    }
    return res;
}

void solve(){
    int size_v,size_e;
    cin >> size_v >> size_e;
    vector<vector<pii>> graph(size_v);
    rep(i,0,size_e){
        int s,t,w;
        cin >> s >> t >> w;
        graph[s].push_back(make_pair(w,t));
        graph[t].push_back(make_pair(w,s));
    }
    cout << prim(graph) << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}

Measured memory_bytes: 6832
#include <bits/stdc++.h>
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=n1;i<(int)(n2);i++)
using namespace std;
typedef long long ll;

signed main()
{
	int N;
	cin >> N;

	vector<char> S(N);
	Rep(i, N) cin >> S[i];

	int slime = 1;

	Rep(i, N-1){
		if(S[i] != S[i+1]) slime++;
	}

	cout << slime;
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vp;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define all(v) v.begin() , v.end()
#define inputv(v,n) rep(i,n){\
    ll x;\
    cin>>x;\
    v.push_back(x);\
    }
const ll INF=99999999999999;
const ll MOD=1000000007;
 
int main() {
  ll n, m;
  cin >> n >> m;
  vector<ll> k;
  vector<vector<ll> > s;
  rep(i,m){
    ll y;
    cin >> y;
    k.push_back(y);
    vector<ll> sik;
    rep(j,k[i]){
      ll x;
      cin >> x;
      sik.push_back(x);
    }
    s.push_back(sik);
  }
  
  vl p;
  inputv(p,m);
  ll ans = 0;
  for(int bit = 0;bit < (1<<n); bit++){
    vector<bool> check(m,true);
    rep(i,m){
      ll count = 0;
      rep(j,k[i]){
        if(bit & (1 << (s[i][j]-1))){
          count++;
        }
      }
      if(count%2 != p[i]){
        check[i] = false;
      }
    }
    bool allcheck = true;
    rep(i,m){
      if(!check[i]){
        allcheck = false;
      }
    }
    if(allcheck) ans++;
  }
  cout << ans;
      
 return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
main(){
  int b[15],v,v1,v2,i,c,j,p;
  float s;
  while(scanf("%d,",&b[1])!=EOF){
    s=b[1];
    c=0;
    for(i=2;i<=10;i++){
      scanf("%d,",&b[i]);
      s+=b[i];
    }
    scanf("%d,%d",&v1,&v2);
    if(v1<v2){
      v=v1;
      j=1;
    }
    else{
      v=v2;
      j=10;
    }
    s/=(v1+v2);
    s*=v;
    if(j==1){
      for(i=j;i<=10;i++){
	c+=b[i];
	if(c>=s){
	  p=i;
	  break;
	}
      }
    }
    else{
      for(i=10;i>0;i--){
	c+=b[i];
	if(c>s){
	  p=i;
	  break;
	}
      }
    }
    printf("%d\n",p);
  }
  return 0;
}

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

int main() {
  vector<vector<int>> c(3,vector<int>(3));
  for(int i = 0;i<3;i++){
    for(int j =0;j<3;j++){
      cin >> c[i][j];
    }
  }
    
 int a1,a2,a3,b1,b2,b3;
 a1 = 0;
 b1 = c[0][0];
 b2 = c[0][1];
 b3 = c[0][2];
 a2 = c[1][0] - b1;
 a3 = c[2][1] - b2;
 bool flag = true;
  vector<int> a = {a1,a2,a3};
  vector<int> b = {b1,b2,b3};
  
  for(int i = 0;i<3;i++){
    for(int j =0;j<3;j++){
      if(c[i][j] != a[i] + b[j]){
        flag = false;
        break;
      }
    }
  }
      if(flag) cout << "Yes" <<endl;
      else cout << "No" << endl;
 }

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

int main(){
 string s;
  cin >> s;
  int ans=0,maxi=0;
  rep(i,s.length()){
    if( s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T'){
    	maxi++;
    }else{
      if(maxi >= ans){
        ans = maxi;
        maxi=0;
      }
    }
  }
  cout << max(ans,maxi) << endl;
}

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

int n;
pair<int, int> teams[100];
int result[100];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) teams[i].second = i;
	for (int i = 0; i < n * (n - 1) / 2; i++) {
		int a, b, pa, pb;
		cin >> a >> b >> pa >> pb;
		a--; b--;
		if (pa > pb) {
			teams[a].first += 3;
		}
		else if (pb > pa) {
			teams[b].first += 3;
		}
		else {
			teams[a].first++;
			teams[b].first++;
		}
	}
	sort(teams, teams + n, greater<pair<int, int> >());
	int rank = 1;
	result[teams[0].second] = 1;
	for (int i = 1; i < n; i++) {
		if (teams[i].first != teams[i - 1].first) rank = i + 1;
		result[teams[i].second] = rank;
	}
	for (int i = 0; i < n; i++) {
		cout << result[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 1164
#include<iostream>
#include<string.h>
using namespace std;

string s;
int cnt=0;
int main()
{
	cin>>s;
	int len=s.length();
	for(int i=0;i<s.length();i++)
	{
		if(s[i]=='S')
			cnt++;
		if(s[i]=='T')
		{
			if(cnt>0)
			{
				cnt--;
				len-=2;
			}
		}	
	} 
	cout<<len<<endl;
	return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
#include<math.h>

int main(){

  long long a,b,c;
  scanf("%lld%lld%lld",&a,&b,&c);
  

  if(c<=a+b){
    printf("Yes");
  }
  else{
    printf("No");
  }
    


  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
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; }
const int INF=1001001001;
vector<pair<int64_t,int64_t>>func(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p;
}
 
 double func(int x){
   int sum=0;
   for(int i=1;i<=x;i++){
     sum+=i;
   }
   return (double)sum/(double)x;
   }
int main() {
  int N,K;
  cin>>N>>K;
  vector<int>p(N+1);
  for(int i=1;i<=N;i++){
   cin>>p[i];
  }
  vector<double>q(N+1);
  double sum=0;
  for(int i=1;i<=N;i++){
   sum+=func(p[i]);
   q[i]=sum;
  }
  double ans=0;
  for(int i=1;i<=N;i++){
   if(i<=N-K+1) {ans=max(ans,q[i+K-1]-q[i-1]);}
  }
  cout<<fixed<<setprecision(10)<<ans<<endl;
  return 0;
}

Measured memory_bytes: 2560
#include <iostream>
using namespace std;
#define N 753
int main(){
  int x,ans=1000;
  string str;
  cin>>str;
  for(int i=0;i+2<str.length();i++){
    x=(str[i]-'0')*100+(str[i+1]-'0')*10+(str[i+2]-'0');
    ans=min(ans,abs(x-N));
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
# coding: utf-8
import sys
from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    SS = read().split()

    for S in SS:
        path = [0]
        for s in S:
            path.append(path[-1]+ dic[s])
        ways.append((path[-1], min(path)))

    ways_pos = sorted([(a,b) for a,b in ways if a >= 0], key = lambda x:x[0], reverse=True)
    ways_neg = sorted([(a,b) for a,b in ways if a < 0], key = lambda x:(x[0] - x[1]), reverse=True)

    tmp = []
    for go, max_depth in ways_pos:
        if current + max_depth >= 0:
            current += go
        else:
            tmp.append((go, max_depth))

    for go, max_depth in tmp:
        if current + max_depth >= 0:
            current += go
        else:
            print('No')
            return None

    tmp =[]
    for go, max_depth in ways_neg:
        if current + max_depth >= 0:
            current += go
        else:
            tmp.append((go, max_depth))

    for go, max_depth in tmp:
        if current + max_depth >= 0:
            current += go
        else:
            print('No')
            return None


    if current == 0:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    run()

Measured memory_bytes: 167216