akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef pair<int, int> pii;
// #define INF __INT32_MAX__
#define INF 1e9
#define LINF __LONG_LONG_MAX__

bool isUpper(char c) {
    return 'A' <= c && c <= 'Z';
}

bool isLower(char c) {
    return 'a' <= c && c <= 'z';
}

int main() {
    string S; cin >> S;
    int N = S.size();

    if (S[0] != 'A') {
        cout << "WA" << endl;
        return 0;
    }

    int cnt = 0;
    int index = -1;
    for (int i = 2; i <= N - 2; i++) {
        if (S[i] == 'C') {
            cnt++;
            index = i;
        }
    }
    if (cnt != 1) {
        cout << "WA" << endl;
        return 0;
    }

    for (int i = 0; i < N; i++) {
        if (i == 0) continue;
        if (i == index) continue;

        if (!isLower(S[i])) {
            cout << "WA" << endl;
            return 0;
        }
    }

    cout << "AC" << endl;
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  int n;
  cin>>n;
  vector<ll> a(n);
  set<ll> st;
  for(int i=0;i<n;i++){
    cin>>a[i];
    st.insert(a[i]);
  }
  sort(a.begin(),a.end());
  vector<ll> vec;
  for(auto &e:st){
    auto l=lower_bound(a.begin(),a.end(),e);
    auto u=upper_bound(a.begin(),a.end(),e);
    if(u-l>=2){
      vec.push_back(e);
    }
    if(u-l>=4){
      vec.push_back(e);
    }
  }
  if(vec.size()<2) {
    cout<<0;
    return 0;
  }
  sort(vec.begin(),vec.end(),greater<int>());
  cout<<(ll)vec[0]*vec[1];
}

Measured memory_bytes: 5760
#include <iostream>
#include <vector>
#include <stdio.h>
#include <cmath>

#include <bits/stdc++.h>
#include <vector>

using namespace std;

#define ipair pair<int,int>
#define rep(I,N) for(int I=0; I<N; I++)
#define rrep(I,N) for(int I=N; I>=0; I--)
#define repj(i,j,n) for(int i=j;i<n;i++)

#define PB(a,i) (a).push_back(i)
#define ALL(a) (a).begin(),(a).end()

#define OK(i) cout<<"OK "<<i<<endl
#define Yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define No cout<<"No"<<endl
#define NO cout<<"NO"<<endl

typedef long long int lli;
typedef long long ll;
typedef vector<int> vi;
typedef vector< vector<int> > Matrix;


bool is_753 (long n)
{
  bool val[10] = {false};
  while (n > 0) {
    int tmp = n % 10;
    // printf("n=%d, tmp = %d\n", n);
    if (!(tmp == 7 ||
          tmp == 5 ||
          tmp == 3)) {
      return false;
    }
    val[tmp] = true;
    n /= 10;
  }
  return (val[3] && val[5] && val[7]);
}


long dfs (long n, long N)
{
  long ans = 0;
  if (n > N) {
    return 0;
  }
  if (is_753(n)) { ans += 1; }
  ans += dfs(n * 10 + 3, N);
  ans += dfs(n * 10 + 5, N);
  ans += dfs(n * 10 + 7, N);

  return ans;
}


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

  printf ("%ld\n", dfs (0, N));

  return 0;
}


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

#ifdef LOCAL

template<class T, class U>
ostream& operator<<(ostream& os, pair<T, U> p) {
	os << "(" << p.first << ", " << p.second << ")";
	return os;
}

template<template<class, class...> class C, class... A>
typename enable_if<!is_same<C<A...>, string>::value, ostream&>::type
operator<<(ostream& os, class C<A...> c) {
	auto i = c.begin();
	while (i != c.end()) {
		os << " {"[i == c.begin()] << *i;
		os << ",}"[++i == c.end()];
	}
	return os;
}

#define debug(x) cerr << #x << " = " << x << endl;
#else
#define debug(...) {}
#endif

const int N = 1e6;
long long infLL = 1e18;
int inf = 1e9;

bool check(int a, int b) {
	return abs(a - b) % 2 == 0;
}

int main() {
	ios_base::sync_with_stdio(false);
	int n, a, b;
	cin >> n >> a >> b;
	cout << (check(a, b) ? "Alice" : "Borys");
}


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

struct Problem {

    UL dp[10001] = {};

    void Solve() {
        UL N, W; cin >> N >> W;
        rep(i, N) {
            UL v, w; cin >> v >> w;
            for (UL t = w; t <= W; t++) {
                dp[t] = max(dp[t], dp[t - w] + v);
            }
        }
        UL ans = 0;
        rep(w, W + 1) ans = max(ans, dp[w]);
        cout << ans << endl;
    }
};
int main() {
    unique_ptr<Problem> p(new Problem());
    cout << fixed << setprecision(10);
    p->Solve();
    return 0;
}



Measured memory_bytes: 3188
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N = NI()
    grid = make_grid(10, 10, 0)
    ans = 0
    for i in range(N+1):
        s = str(i)
        t = int(s[0])
        b = int(s[-1])
        grid[t][b] += 1
    for i in range(1, 10):
        for j in range(1, 10):
            ans += grid[i][j] * grid[j][i]
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 9440
/*
              *******
When winter comes,You'll hear no lions roar,
no stags grazing the fields,
no roses growing in the meadows,
no snakes in the sand.
The krakens will freeze where they swim.
The flayed men will rot and wither.
No trouts swimming in the river and no falcons flying in the air.
Not even the dragons breath will warm you in your halls.
Only the wolfs howl in the night.
            WINTER IS COMING
*/
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define si(x) scanf("%d",&x)
#define pi(x) printf("%d\n",x)
#define s(x) scanf("%lld",&x)
#define p(x) printf("%lld\n",x)
#define sc(x) scanf("%s",x)
#define pc(x) printf("%s",x)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define inf 2e18
#define prec(x) fixed<<setprecision(15)<<x
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mem(x,y) memset(x,y,sizeof(x))
#define PQG priority_queue< int,std::vector<int>,std::greater<int> >
#define PQL priority_queue< int,std::vector<int>,std::less<int> >
#define PQPL priority_queue<pii ,vector< pii >, less< pii > >
#define PQPG priority_queue<pii ,vector< pii >, greater< pii > >
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)

using namespace std;

int main() {
    fast_io;
    int n,m; cin>>n>>m;
    int cnt[n+5];
    mem(cnt,0);
    for(int i=0;i<m;i++) {
        int l,r; cin>>l>>r;
        cnt[l]++, cnt[r+1]--;
    }
    for(int i=1;i<=n;i++) {
        cnt[i]+=cnt[i-1];
    }
    int ans=0;
    for(int i=1;i<=n;i++) {
        if(cnt[i]>=m) ans++;
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 640
#どっちで出すか注意, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    A = list(map(int, input().split()))
    C = Counter(A)
    total = 0
    for i in C.values():
        if i == 1:
            continue
        total += i*(i-1)//2
    
    for i in range(N):
        a = C[A[i]] - 1
        print(total - a)


if __name__ == '__main__':
    main()


Measured memory_bytes: 25920
#include <stdio.h>
#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <stdio.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <list>
#include <utility>
#include <set>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <random>

using namespace std;

static const double EPS = 1e-9;
template<class T> bool INRANGE(T x, T a, T b) { return a <= x && x <= b; }
template<class T> void amin(T &a, T v) { if (a > v) a = v; }
template<class T> void amax(T &a, T v) { if (a < v) a = v; }
int ROUND(double x) { return (int)(x + 0.5); }
bool ISINT(double x) { return fabs(ROUND(x) - x) <= EPS; }
bool ISEQUAL(double x, double y) { return fabs(x - y) <= EPS * max(1.0, max(fabs(x), fabs(y))); }
double SQSUM(double x, double y) { return x * x + y * y; }
#define PI  (acos(-1))
#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0])) 
#define NG (-1)
#define BIG ((int)1e9+10)
#define BIGLL ((ll)4e18)
#define SZ(a) ((int)(a).size())
#define SQ(a) ((a)*(a))
typedef unsigned long long ull;
typedef long long ll;



int N, K;
vector <vector <int> > adj;

ll ans = 1;

enum { NUM_FACTORIAL = 1012345 };
ll f[NUM_FACTORIAL];
ll f_inv[NUM_FACTORIAL];
ll MOD = (ll)1e9 + 7LL;


ll extgcd(ll a, ll b, ll& x, ll& y)
{
	ll d = a;
	if (b != 0)
	{
		d = extgcd(b, a%b, y, x);
		y -= (a / b)*x;
	}
	else
	{
		x = 1;
		y = 0;
	}
	return d;
}

// 逆元を求める
ll mod_inverse(ll a, ll m)
{
	ll x, y;
	extgcd(a, m, x, y);
	return (m + x % m) % m;
}


void mod_factorial_init()
{
	f[0] = 1;
	for (int i = 1; i < NUM_FACTORIAL; ++i)
	{
		f[i] = f[i - 1] * i;
		f[i] %= MOD;
	}

	for (int i = 0; i < NUM_FACTORIAL; ++i)
	{
		f_inv[i] = mod_inverse(f[i], MOD);
	}
}


void dfs(int now, int prev, int depth)
{

	int numChild = SZ(adj[now]);



	if (depth > 0)
	{
		numChild--;
	}

	if (depth == 0)
	{
		ans *= K;
		ans %= MOD;
	}


	{
		ll x = K - min(2, depth+1);
		ll y = x - numChild;

		// BEGIN CUT HERE
//		cerr << " numChild=" << numChild << endl;
		// END CUT HERE


		

		if (x >= y && x>=0 && y>=0)
		{
			ans *= f[x];
			ans %= MOD;
			ans *= f_inv[y];
			ans %= MOD;

			// BEGIN CUT HERE
//			cerr << " now=" << now << " prev=" << prev << " depth=" << depth << " x=" << x << " y=" << y << " ans=" << ans << endl;
			// END CUT HERE

		}
		else
		{
			ans *= 0;
		}
	}

	for (int a : adj[now])
	{
		if (a != prev)
		{
			dfs(a, now, depth + 1);
		}
	}
}

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

	mod_factorial_init();
	adj.resize(N);

	for (int i = 0; i < N-1; ++i)
	{
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	dfs(0, NG, 0);

	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 25088
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int A,B,C,D,E,F,G,H,I,g;
    cin>>A>>B>>C>>D>>E>>F;
    g=min(min(min(C,D),A),B);
    G=(A+B+C+D)-g;
    H=max(E,F);
    I=G+H;
    cout<<I<<endl;
    return 0;
}



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

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

    int ans=n;

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if(i==j)continue;
            long p=x[i]-x[j];
            long q=y[i]-y[j];
            int sum=0;
            for (int k = 0; k < n; k++){
                for (int l = 0; l < n; l++){
                    if((p==x[k]-x[l])&&(q==y[k]-y[l])){
                        sum++;
                    }
                }
            }
            ans=min(ans,n-sum);
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

int main(void){
    int n,a,b,c,x;
    while(cin>>n>>a>>b>>c>>x,n){
        deque<int> r(n);
        rep(i,n) cin>>r[i];
        rep(i,10001){
            if(x==r[0]) r.pop_front();
            if(r.size()==0){
                cout<<i<<endl;
                break;
            }
            x=(a*x+b)%c;
        }
        if(r.size()!=0) cout<<-1<<endl;
    }
}

Measured memory_bytes: 3008
/*
"Won't stop until I'm phenomenal."
- Phenomenal, Eminem
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define ff first
#define Shazam ios_base::sync_with_stdio(false);   cin.tie(NULL); cout.tie(NULL);
#define ss second
#define all(c) c.begin(),c.end()
#define endl "\n"
#define test() int t; cin>>t; while(t--)
#define fl(i,a,b) for(int i = a ; i <b ;i++)
#define get(a) fl(i,0,a.size())  cin>>a[i];
#define pra(a) fl(i,0,a.size()) cout<<a[i]<<" ";	cout<<endl;
#define pr(a,n) fl(i,0,n) cout<<a[i]<<" ";	cout<<endl;
const ll INF = 2e18;
const int inf = 2e9;
const int mod1 = 1e9 + 7;



int main(){
    Shazam;

    int n; cin>>n;
    ll k; cin>>k;
    vector<ll> a(n);
    for(ll &i : a) cin>>i;
    sort(all(a));
    ll hi = 2e18+1;
    ll lo = -2e18;
    while(hi - lo > 1){
        ll m = lo + (hi-lo)/2;
        ll sum = 0;
        for(int i = 0 ; i < n; i++){
            if(a.at(i)>0) sum += lower_bound(a.begin(),a.end(), (long double)(m)/a.at(i)) - a.begin();
            if(a.at(i)<0) sum += n - (upper_bound(a.begin(),a.end(),(long double)(m)/a.at(i)) - a.begin());
            if(a.at(i)==0) sum += ((m>0)?n:0);
            if(a.at(i)*a.at(i) < m) sum--; 
        }
        if(sum/2 < k)
            lo = m;
        else
            hi = m;
    }
    cout<<lo<<endl;

    return 0;
}

Measured memory_bytes: 4748
x = int(input())
p_list = {}


def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

for i in range(1,x+1):
    for k in prime_factors(i):
        p_list[k] = p_list.get(k, 0) + 1

# del p_list[1]

divn = 1e9+7
ans = 1
for k in p_list.keys():
    ans *= p_list[k] + 1
    ans = ans % divn

print(int(ans))

Measured memory_bytes: 3064
if ARGV[0]=="LOCAL_DEV"
  define_method("debug") do |var|
    p var
  end
else
  define_method("debug") do |var|
  end
end

N,Z,W = STDIN.gets.strip.split.map(&:to_i)
a = STDIN.gets.strip.split.map(&:to_i)
debug(a)
puts [(W-a[N-1]).abs , (a[N-2]-a[N-1]).abs].max


Measured memory_bytes: 1916
S = [str(i) for i in input()]
stuckS = []
for i in range(len(S)):
    if S[i] == "B":
        if len(stuckS) == 0:
            continue
        else:
            stuckS.pop()
    else:
        stuckS.append(S[i])

ans = "".join(stuckS)
print(ans)

Measured memory_bytes: 3060
#include <iostream>
 using namespace std;
 int main(){
 long long a, b, k;
 cin >> a >> b >> k;
 if(k <= a){
 cout << a - k << ' ' << b <<endl;
}else if(k <= a+b){
 cout << 0 << " " << b - (k-a) <<endl;
 }else{
  cout << 0 << " " << 0 <<endl;}}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define arep(i, x, n) for (int i = int(x); i < (int)(n); i++)
#define rep(i, n) for (long long i = 0; i < n; ++i)
#define pi 3.141592653589793
#define eps 0.00000001
#define INF 1e9 + 7
using ll = long long;

string s;

int main() {
    cin >> s;
    cout << s.substr(0, 3) << endl;


    return 0;
}

Measured memory_bytes: 3624
T = input().strip()
n = len(T)

p = n // 2
g = n - p

A = 'g' * g + 'p' * p

ans = 0
for a, t in zip(A, T):
    if a == 'p' and t == 'g':
        ans += 1
    if a == 'g' and t == 'p':
        ans -= 1

print(ans)




Measured memory_bytes: 3316
from itertools import accumulate

N, K = map(int, input().split())
S = [int(x) for x in input()]

nums = []
now, cnt = 1, 0
for s in S:
    if s == now:
        cnt += 1
    else:
        nums.append(cnt)
        now, cnt = 1 - now, 1
if cnt != 0:
    nums.append(cnt)
if len(nums) % 2 == 0:
    nums.append(0)

sums = [0] + list(accumulate(nums))

ans = 0
add = 2 * K + 1
for i in range(0, len(nums), 2):
    left = i
    right = min(i + add, len(nums))
    ans = max(ans, sums[right] - sums[left])
print(ans)


Measured memory_bytes: 9372
#include <stdio.h>
int main()
{
    int n, x;
    do
    {
         scanf("%d %d", &n, &x);
        if (n != 0 || x != 0)
        {
            int count = 0;
            for (int a = 1; a <= n; a++)
            {
                for (int b = 1; b <= n; b++)
                {
                    for (int c = 1; c <= n; c++)
                    {
                        if (a < b && b < c && a + b + c == x)
                        {
                            count=count + 1;
                        }
                    }
                }
            }

            printf("%d\n", count);
        }
    } while (n != 0 || x != 0);
    
    return 0;
}


Measured memory_bytes: 2696
#include <stdio.h>

int main(void) {
	int a, b, c;
	if (scanf("%d%d%d", &a, &b, &c) != 3) return 1;
	if (a > b && a > c) puts("A");
	else if (a < b && b > c) puts("B");
	else puts("C");
	return 0;
}



Measured memory_bytes: 2144
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(12);

    int n; 
    cin >> n;
    int mx = 101;

    auto calc = [&](int a, int b, int c) {
        int res = a * a + b * b + c * c + a * b + a * c + b * c;
        return res;
    };

    vector<int> cnts(n + 1, 0);
    for (int i = 1; i <= mx; ++i) {
        for (int j = 1; j <= mx; ++j) {
            for (int k = 1; k <= mx; ++k) {
                int N = calc(i, j, k);
                if (N <= n) {
                    ++cnts[N];
                }
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        cout << cnts[i] << '\n';
    }

    return 0;
}

Measured memory_bytes: 3576
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
	int N; cin >> N;
	int ans = 0;
	for (ll n = 1; n < N; n *= 3) ans++;
	cout << ans << endl;
}

Measured memory_bytes: 1164
#include <iostream>

using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)

int main() {
	char X, Y; cin >> X >> Y;
	cout << ((X < Y) ? '<' : (X != Y) ? '>' : '=') << endl;

	return 0;
}

Measured memory_bytes: 256
import itertools

def bit(n, k):
    s = [0 for _ in range(k)]
    u = n
    b = 0
    while(u > 0):
        s[k-1-b] += u % 2
        u = u // 2
        b += 1
    return s

h, w, k = map(int, input().split())
c = []
for _ in range(h):
    c.append(input())
    
tate = [0 for _ in range(w)]
yoko = [0 for _ in range(h)]
for i in range(w):
    for j in range(h):
        if(c[j][i] == "#"):
            tate[i] += 1
for i in range(h):
    yoko[i] += c[i].count("#")
m = sum(yoko)

ans = 0
for i in range(2**h):
    for j in range(2**w):
        g = m
        comb_s = bit(i, h)
        comb_t = bit(j, w)
        for p in range(h):
            if(comb_s[p] == 1):
                g -= yoko[p]
        for q in range(w):
            if(comb_t[q] == 1):
                g -= tate[q]
        for p in range(h):
            for q in range(w):
                if(c[p][q] == "#" and comb_s[p] == 1 and comb_t[q] == 1): 
                    g += 1
        if(g == k):
            ans += 1
print(ans)
                
                     
        






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

using namespace std;

int main(){
    string S;
    cin >> S;
    bool flag1 = false;
    bool flag2 = false;
    bool flag3 = false;

    if(S[0] == 'A'){
        flag1 = true;
    }

    int count = 0;
    for(int i=2; i< S.size()-1; i++){
        if(S[i]=='C'){
            count++;
        }
    }
    if(count == 1){
        flag2 = true;
    }

    int small = 0;
    for(int i=0; i<S.size(); i++){
        if(S[i] >= 'a' && S[i] <= 'z'){
            small++;
        }
    }
    if(small == S.size()-2){
        flag3 = true;
    }
    
    if(flag1 == true && flag2 == true && flag3 == true){
        cout << "AC" << endl;
    }else{
        cout << "WA" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows;

namespace AtCoder
{
    class Program
    {
        
        static void Main()
        {
            //ここから
            int N = ReadLineToInt();
            long[][] point = new long[N][];
            for(int i = 0; i < N; i++)
            {
                long[] temp = ReadLineToLongArray();
                point[i] = temp;
            }

            point = point.OrderByDescending(p => p[2]).ToArray();

            long[] ans = new long[3];
            for(long x = 0; x < 101; x++)
            {
                for(long y = 0; y < 101; y++)
                {
                    long H = Math.Abs(point[0][0] - x) + Math.Abs(point[0][1] - y) + point[0][2];

                    bool flag = true;

                    for (int i = 0; i < N; i++)
                    {
                        if( point[i][2] != Math.Max( H - Math.Abs(point[i][0] - x) - Math.Abs(point[i][1] - y ), 0 ))
                        {
                            flag = false;
                            break;
                        }
                    }

                    if (flag)
                    {
                        ans[0] = x;
                        ans[1] = y;
                        ans[2] = H;
                    }
                }
            }



            //ここまで
            Console.WriteLine(ans[0]+" "+ans[1]+" "+ans[2]);
            Console.ReadKey();
        }


        static public void Swap<T>(ref T a,ref T b) { T temp = a;a = b;b = temp; }
        static public long GCD(int a, int b){ return b != 0 ? GCD(b, a % b) : a;}
        static public long LCM(int a, int b){ return (long)a * b / GCD(a, b); }
        static public int Factorial(int a) { return a == 1 ? a : a * Factorial(a - 1); }
        static public int Conbin(int n,int m) { return Factorial(n) / (Factorial(n - m) * Factorial(m)); }


        
        static public string ReadLineToString(){return Console.ReadLine();}
        static public int ReadLineToInt(){return int.Parse(Console.ReadLine());}
        static public long ReadLineToLong() { return long.Parse(Console.ReadLine()); }
        static public string[] ReadLineToStringArray(){return Console.ReadLine().Split(' ').ToArray();}
        static public int[] ReadLineToIntArray(){return Console.ReadLine().Split(' ').Select(int.Parse).ToArray();}
        static public long[] ReadLineToLongArray() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
        static public List<string> ReadLineToStringList(){return Console.ReadLine().Split(' ').ToList();}
        static public List<int> ReadLineToIntList(){return Console.ReadLine().Split(' ').Select(int.Parse).ToList();}
        static public List<long> ReadLineToLongList() { return Console.ReadLine().Split(' ').Select(long.Parse).ToList(); }
    }
    
}


Measured memory_bytes: 13524
#include<iostream>
using namespace std;
const int MAX_T = 3000, MAX_M=300;

int M, start, goal,dice[6], *N;

enum status{GOOD, SOSO, BAD};
bool isPositionValid(int p){return 0<=p && p<M;}

int* MakePath(int *path, int from){
	static bool visit[MAX_M] = {};
	static auto checkPath = [&path](int moveto)->int{
		if(!isPositionValid(moveto)){
			return 2*MAX_T;
		}
		else{
			int position = moveto+ N[moveto];
			if(!visit[position]) MakePath(path, position);
			return  path[position]+1;
		}
	};

	if(path==NULL){
		path = new int[M];
		for(int m=0; m<M; m++) path[m] = MAX_T+1;
	}

	visit[from] = true;
	int bestpath = MAX_T;
	if(from==goal)	bestpath = 0;
	else{
		for(int r=0; r<6; r++){
			bestpath = min(bestpath, checkPath(from + dice[r]));
			bestpath = min(bestpath, checkPath(from - dice[r]));
		}
	}
	path[from] = bestpath;
	return path;
}

int main(){
	// 入力
	cin >> M;
	N = new int[M];
	for(int r=0; r<6; r++)	cin >> dice[r];
	cin >> start >> goal;
	for(int m=0; m<M; m++)	cin >> N[m];
	start--;
	goal--;

	int* path = MakePath(NULL, start);
	
	//本番
	int position = start;
	for(int t=0; t<MAX_T; t++){
		if(position == goal) break;
	
		int r;
		cin >> r;
		int d = dice[r-1];

		static auto tryMove = [&path](int moveto, int path_before)->status{
			if(isPositionValid(moveto)){
				int path_new = path[moveto + N[moveto]];
				if(path_before > path_new) return GOOD;
				else if(path_before == path_new) return SOSO;
			}
			return BAD;
		};
	
		int output = 0;
		status forward_status, backward_status;
		forward_status  = tryMove(position + d, path[position]);
		if(forward_status == GOOD) output = 1;

		if(output==0){
			backward_status = tryMove(position - d, path[position]);
			if(backward_status == GOOD) output = -1;
		}

		if(output==0){
			if(forward_status==SOSO) output=1;
			else if(backward_status == SOSO)output=-1;
		}

		position = position + output*d  + (output==0?0:N[position + output*d]);
		cout << output << endl;
	}

	delete[] N;
	delete[] path;
	return 0;
}

Measured memory_bytes: 1308
#include <bits/stdc++.h>
#define make_pair mp
#define pii pair<int,int>
using namespace std;
typedef long long ll;
const int maxn=100007;
const int inf=(1LL<<29);
int main(){
    int a,b,c;cin>>a>>b>>c;
    cout<<min(b/a,c);
    return 0;
}


Measured memory_bytes: 256
/**
 *    author:  tourist
 *    created: 27.11.2019 08:48:17       
**/
#include <bits/stdc++.h>

using namespace std;

struct Point {
  int x;
  int y;
};

void MoveX(vector<Point>& p, int x) {
  for (auto& q : p) {
    if (q.x >= x) {
      ++q.x;
    }
  }
}

void MoveY(vector<Point>& p, int y) {
  for (auto& q : p) {
    if (q.y >= y) {
      ++q.y;
    }
  }
}

int Signum(int x) {
  return (x > 0 ? 1 : (x < 0 ? -1 : 0));
}

vector<Point> Solve(const vector<int>& a) {
  if (a.size() == 4) {
    return {{0, 0}, {1, 0}, {1, 1}, {0, 1}};
  }
  int n = (int) a.size();
  for (int i = 0; i < n - 1; i++) {
    if (a[i] + a[i + 1] == 360) {
      vector<int> b = a;
      b.erase(b.begin() + i, b.begin() + i + 2);
      auto p = Solve(b);
      int pr = (i == 0 ? n - 3 : i - 1);
      int ne = (i == n - 2 ? 0 : i);
      MoveX(p, p[pr].x + 1);
      MoveX(p, p[pr].x);
      MoveY(p, p[pr].y + 1);
      MoveY(p, p[pr].y);
      Point u = p[pr];
      Point v = p[ne];
      if (u.x == v.x) {
        int dy = (u.y > v.y ? -1 : 1);
        int dx = Signum(p[(pr + n - 3) % (n - 2)].x - u.x);
        if (b[pr] != a[i]) {
          dx *= -1;
        }
        p[ne].x += dx;
        p.insert(p.begin() + i, {u.x, u.y + dy});
        p.insert(p.begin() + i + 1, {u.x + dx, u.y + dy});
      } else {
        int dx = (u.x > v.x ? -1 : 1);
        int dy = Signum(p[(pr + n - 3) % (n - 2)].y - u.y);
        if (b[pr] != a[i]) {
          dy *= -1;
        }
        p[ne].y += dy;
        p.insert(p.begin() + i, {u.x + dx, u.y});
        p.insert(p.begin() + i + 1, {u.x + dx, u.y + dy});
      }
      return p;
    }
  }
  assert(false);
  return {};
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  int sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    sum += a[i];
  }
  if (n % 2 == 1 || sum != 180 * (n - 2)) {
    cout << -1 << '\n';
    return 0;
  }
  auto res = Solve(a);
  for (auto& p : res) {
    cout << p.x << " " << p.y << '\n';
  }
  return 0;
}


Measured memory_bytes: 1280
n,q=map(int,input().split())
N=n

data = [0]*(N+1)
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k

def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s

c=[int(i) for i in input().split()]
Q=[]
for i in range(q):
    l,r=map(int,input().split())
    Q.append((l,r,i))
Ans=[0 for i in range(q)]
F=[-1 for i in range(5*10**5+1)]
Q.sort(key=lambda x:x[1])
#Q.append((10**6,10**6,10**6))

for i in range(n):
    add(i+1,1)

"""
quen=0
nowQ=Q[quen]
for i in range(n):
    ci=c[i]
    if F[ci]>=0:
        add(F[ci]+1,-1)
    F[ci]=i
    while nowQ[1]==i+1:
        Ans[nowQ[2]]=-get(nowQ[0]-1)+get(nowQ[1])
        quen+=1
        nowQ=Q[quen]
    if nowQ[1]==10**6:
        break
"""

i=0
for nowQ in Q:
    while nowQ[1]!=i:
        ci=c[i]
        if F[ci]>=0:
            add(F[ci]+1,-1)
        F[ci]=i
        i+=1
    Ans[nowQ[2]]=-get(nowQ[0]-1)+get(nowQ[1])


print("\n".join([str(i) for i in Ans]))

Measured memory_bytes: 274900
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<set>
#include<unordered_set>
typedef long long int ll;
#define REP(i,n) for(int i=0;i<signed(n);i++)
using namespace std;
const ll MOD = 1000000007;
const ll INF = 9e9;
ll N,M,ans=INF;
ll A[300010],S[301000];
int main(){
    std::ios_base::sync_with_stdio(false);
    cin>>N;
    REP(i,N){
        cin>>A[i];
        S[i]+=A[i];
        S[i+1]=S[i];
    }
    //a:右半分の区切り i:真ん中 b:左半分
    //s:右の和 t:左の和
    ll a=0,b=2,s,t;
    REP(i,N-2){
        if(i==b)b++;
        s=(S[i]-S[a])-S[a];
        t=(S[N-1]-S[b])-(S[b]-S[i]);
        bool f=true;
        if(i==0)continue;
        while(f){
            f=false;
            if(a+1==i)continue;
            if(abs(s)>abs(s-A[a+1]*2)){
                s-=A[a+1]*2;
                a++;f=true;
            }
        }
        f=true;
        while(f){
            f=false;
            if(b+1==N-1||b==N-1)continue;
            if(abs(t)>abs(t-A[b+1]*2)){
                t-=A[b+1]*2;
                b++;f=true;
            }
        }
        ans=min( ans,( max({S[a],S[i]-S[a],S[b]-S[i],S[N-1]-S[b]})
        -min({S[a],S[i]-S[a],S[b]-S[i],S[N-1]-S[b]}) ) );
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3840
N = int(input())
for i in range(N):
    r, t = map(int, input().split())
    p = r // 100 + t // 30 * 5
    if r % 100 == 0:
        if t % 30 == 0:
            print(p)
        else:
            print(p, p+5)
    else:
        if t % 30 == 0:
            print(p, p+1)
        else:
            print(p, p+1, p+5, p+6)



Measured memory_bytes: 5596
$m = {}
def r m, a, b, c
  if $m[[m,a,b,c]]
    return $m[[m,a,b,c]]
  elsif m < 0
    return
  elsif m == 0
    p = 0;
    k = a % 5; p += 380 * k + (380 * (a - k) * 0.80).to_i;
    k = b % 4; p += 550 * k + (550 * (b - k) * 0.85).to_i;
    k = c % 3; p += 850 * k + (850 * (c - k) * 0.88).to_i;
    return $m[[m,a,b,c]] = p
  end
  s = []
  if m >= 200
    s.push r(m - 200, a + 1, b, c)
  end
  if m >= 300
    s.push r(m - 300, a, b + 1, c)
  end
  if m >= 500
    s.push r(m - 500, a, b, c + 1)
  end
  return $m[[m,a,b,c]] = s.select{|a|a}.min
end

while 0 < m = gets.to_i
  p r(m, 0, 0, 0)
end

Measured memory_bytes: 8124
t = int(input())
l=[list(map(int,input().split())) for i in range(t)]
from collections import defaultdict

def solve(n):
    if n==1:
        return d
    if n==0:
        return 0
    if memo[n] != -1:
        return memo[n]

    ret = []
    ret.append(d*n)

    if n%2==0:
        ret.append(a + solve(n//2))
    else:
        ret.append(d + a + solve((n+1)//2))
        ret.append(d + a + solve((n-1)//2))

    if n%3==0:
        ret.append(b + solve(n//3))
    else:
        if (n+1)%3==0:
            ret.append(d + b + solve((n+1)//3))
        else:
            ret.append(d + b + solve((n-1)//3))

    if n%5==0:
        ret.append(c + solve(n//5))
    else:
        if (n-2)%5==0:
            ret.append(2*d + c + solve((n-2)//5))
        elif (n-1)%5==0:
            ret.append(d + c + solve((n-1)//5))
        elif (n+1)%5==0:
            ret.append(d + c + solve((n+1)//5))
        elif (n+2)%5==0:
            ret.append(2*d + c + solve((n+2)//5))

    memo[n]=min(ret)

    return min(ret)

for tmp in l:
    n,a,b,c,d=tmp

    memo=defaultdict(lambda: -1)
    ans = solve(n)
    print(ans)

Measured memory_bytes: 98052
def main():
    s = str(input())
    n = len(s)
    ans = [0] * n
    for i in range(n):
        if s[i] == "R":
            if i != (n - 1) and s[i + 1] == "L":
                ans[i] += 1
                for j in range(i - 2, -1, -2):
                    if s[j] == "R" and s[j + 1] == "R":
                        ans[i] += 1
                    else:
                        break
            for j in range(i + 2, n, 2):
                if s[j - 1] == "L" and s[j] == "L":
                    ans[i] += 1
                else:
                    break
        else:  # s[i] == "L"
            if i != 0 and s[i - 1] == "R":
                ans[i] += 1
                for j in range(i + 2, n, 2):
                    if s[j - 1] == "L" and s[j] == "L":
                        ans[i] += 1
                    else:
                        break
            for j in range(i - 2, -1, -2):
                if s[j] == "R" and s[j + 1] == "R":
                    ans[i] += 1
                else:
                    break
    print(*ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 6400
using System;

namespace ABC092
{
    public class Problem_D
    {
        const int SIZE = 100;
        const int HALF = SIZE / 2;

        public static void Main(string[] args)
        {
            var grid = new char[SIZE][];
            var inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int white = inputs[0], black = inputs[1];
            for (var i = 0; i < SIZE; i++)
            {
                var line = new char[SIZE];
                for (var j = 0; j < SIZE; j++)
                {
                    if (j < HALF) line[j] = '.';
                    else line[j] = '#';
                }
                grid[i] = line;
            }

            for (var b = 0; b < black - 1; b++)
            {
                var col = (b * 2) % HALF;
                var row = (b * 2) >= HALF ? 1 + ((b * 2) / HALF) * 2 : 1;
                grid[row][col] = '#';
            }

            for (var w = 0; w < white - 1; w++)
            {
                var col = (HALF + 1) + (w * 2) % HALF;
                var row = col >= HALF ? 1 + ((w * 2) / HALF) * 2 : 1;
                grid[row][col] = '.';
            }

            Console.WriteLine($"{SIZE} {SIZE}");
            for (var i = 0; i < SIZE; i++)
            {
                Console.WriteLine(string.Join("", grid[i]));
            }
        }
    }
}


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

using namespace std;
#define inf             0x3f3f3f3f
#define INF             2e18
#define eps             1e-9

#define FastRead        ios_base::sync_with_stdio(0);cin.tie(0)
#define fRead           freopen("input.txt","r",stdin)
#define fWrite          freopen("output.txt","w",stdout)

#define LL              long long
#define ull            unsigned long long
#define PI              acos(-1.0)
#define pb              push_back
#define mk              make_pair
#define pii             pair<int,int>
#define pLL             pair<LL,LL>
#define ff              first
#define ss              second
#define all(a)          a.begin(),a.end()
#define SQR(a)          ((a)*(a))
#define min3(a,b,c)     min(a,min(b,c))
#define max3(a,b,c)     max(a,max(b,c))
#define min4(a,b,c,d)   min(min(a,b),min(c,d))
#define max4(a,b,c,d)   max(max(a,b),max(c,d))
#define max5(a,b,c,d,e) max(max3(a,b,c),max(d,e))
#define min5(a,b,c,d,e) min(min3(a,b,c),min(d,e))
#define vi              vector <int>
#define vL              vector <LL>
#define LB(a,x)         (lower_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which does not compare less than val.
#define UB(a,x)         (upper_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which compares greater than val.
#define prec(n)         fixed << setprecision(n)

#define MEM(a,x)        memset(a,x,sizeof(a))
#define SORT(v)         sort(v.begin(),v.end())
#define REV(v)          reverse(v.begin(),v.end())
#define Unique(a)       sort(all(a)),a.erase(unique(all(a)),a.end())

#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)
#define IT(it,x)	    for(it=x.begin();it!=x.end();it++)
int main()
{
    LL x,n;
    cin>>x>>n;
    LL s=0;
    for(int i=0;i<n;i++)
    {
        LL a;
        cin>>a;
        s+=a;
    }
    if(s>=x)
        cout<<"Yes";
    else
        cout<<"No";

}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int main(void){
	
	int a,b,c,d,i,s=0;
	
	cin>>a>>b;
	
	c=b-a;
	
	for(i=1;i<=c;i++){
		s=s+i;
	}
	
	d=s-b;
	
	cout<<d<<endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
int main(){
int A,B,C,D;
std::cin >> A >> B ;
if(A%3==0 || B%3==0 || (A+B)%3==0)
std::cout << "Possible" << std::endl;
else
std::cout << "Impossible" << std::endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

int d[101][101];
int inf=INT_MAX;
int v;
int warshall_floyd(){
    rep(k,v)rep(i,v)rep(j,v){
        if(d[i][k]==inf||d[k][j]==inf)continue;
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    }
}
int main(){
    int e,r,s,t,ds;
    cin>>v>>e;
    rep(i,v)rep(j,v) d[i][j]=inf;
    rep(i,v) d[i][i]=0;
    rep(i,e){
        cin>>s>>t>>ds;
        d[s][t]=ds;
    }
    warshall_floyd();
    rep(i,v){
        if(d[i][i]<0){
            cout<<"NEGATIVE CYCLE"<<endl;
            break;
        }
        else if(i==v-1){
            rep(j,v){
                rep(k,v){
                    if(d[j][k]<inf) cout<<d[j][k];
                    else cout<<"INF";
                    if(k==v-1) cout<<endl;
                    else cout<<" ";
                }
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3136
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n+m; i++)
#define ALL(v) v.begin(), v.end()

using ll = long long;
using ull = unsigned long long;
using namespace std;

int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<char> > a(H, vector<char>(W));
    vector<vector<char> > b(H+2, vector<char>(W+2));
    REP(i, H+2) {
        REP(j, W+2) {
            b[i][j] = '#';
        }
    }
    REP(i, H) {
        REP(j, W) {
            cin >> a[i][j];
            b[i+1][j+1] = a[i][j];
        }
    }
    REP(i, H+2) {
        REP(j, W+2) {
            cout << b[i][j];
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int A[5000], B[5000], i, j, a, b, ans = 0;
  scanf("%d%d", &a, &b);
  for(i = 0;i < a;i++){
    scanf("%d", A + i);
  }
  for(i = 0;i < b;i++){
    scanf("%d", B + i);
  }
  for(i = 0;i < b;i++){
    int k = 0;
    for(j = 0;j < a;j++){
      if(i + k >= b)break;
      if(B[i + k] == A[j])k++;
    }
    if(k > ans){
      ans = k;
    }
  }
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 636
#include "bits/stdc++.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define FOR(i,init,a) for(int i=init; i<a; i++)
#define rep(i,a) FOR(i,0,a)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()
#define chmin(a,b) a=min(a,b);
#define chmax(a,b) a=max(a,b);

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll N,A,B;
    cin>>N>>A>>B;
    
    ll ans;
    if(N==1){
        ans=(A==B);
    }else{
        if(A>B){
            ans=0;
        }else{
            ans=(B-A)*(N-2)+1;
        }
    }
    cout1(ans)
}

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

using in = int64_t;

int main(){
in n,m;
  cin >>n>>m;
priority_queue<double> a;
  rep(i,n){ 
    double z;
    cin>>z;
    a.push(z);
  }
  
  rep(i,m){
    double x = a.top();
    a.pop();
    a.push(x/2);
    
  }
  
  in ans =0;
  rep(i,n){
  ans += (in)a.top();
    a.pop();
  }
  
  cout <<ans<<endl;
}


Measured memory_bytes: 1400
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}
struct UnionFind {
    int n, cc, *u;
    UnionFind() : n(0), cc(0), u(NULL) {}
    UnionFind(int n_) : n(n_), cc(n_) {
	u = new int[n_];
	memset(u, -1, sizeof (int) * n);
    }
    UnionFind(const UnionFind &y) : n(y.n), cc(y.cc) {
	u = new int[y.n];
	memcpy(u, y.u, sizeof (int) * n);
    }
    ~UnionFind() {
	delete[] u; u = NULL;
	n = cc = 0;
    }
    friend void swap(UnionFind &x, UnionFind &y) {
	swap(x.n, y.n); swap(x.cc, y.cc); swap(x.u, y.u);
    }
    UnionFind& operator=(UnionFind y) { 
	swap(*this, y);
	return *this;
    }
    int root(int x) {
	int y = x, t;
	while (u[y] >= 0) y = u[y];
	while (x != y) { t = u[x]; u[x] = y; x = t; }
	return y;
    }
    bool link(int x, int y) {
	x = root(x); y = root(y);
	if (x == y) return false;
	if (u[y] < u[x]) swap(x, y);
	u[x] += u[y]; u[y] = x; cc--;
	return true;
    }
    bool same(int x, int y) { return root(x) == root(y); }
    int size(int x) { return -u[root(x)]; }
    int count() { return cc; }
};

int N, M, K;

struct Edge {
    int x, y, c;
    Edge(){}
    Edge(int x_, int y_, int c_) {
	x = x_;
	y = y_;
	c = c_;
    }

    bool operator<(const Edge &o) const {
	return c < o.c;
    }
} E[100011];
int C[100011];

void MAIN() {
    scanf("%d%d%d", &N, &M, &K);
    REP (i, N) scanf("%d", C+i);
    int color = K+1;
    REP (i, N) if (C[i] == 0) C[i] = color++;
    
    REP (i, M) {
	int x, y, c;
	scanf("%d%d%d", &x, &y, &c);
	x--; y--;
	E[i].x = x;
	E[i].y = y;
	E[i].c = c;
    }
    sort(E, E+M);
    UnionFind U(color);
    LL ans = 0;
    int cnt = 0;
    REP (i, M) {
	if (cnt == K-1) break;
	int cx = C[E[i].x];
	int cy = C[E[i].y];
	if (!U.same(cx, cy)) {
	    ans += E[i].c;
	    U.link(cx, cy);
	    cnt++;
	}
    }
    if (cnt < K-1) {
	puts("-1");
    } else {
	printf("%lld\n", ans);
    }
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define rep(i,n) for (int (i) = 0; (i) < (n); i++)
#define ll long long
using namespace std;
int main() {
  int N = 0,M = 0;
  cin >> N >> M;
  if(M == 1){
    cout << (1900 * M + 100 * (N - M)) * 2;
  }
  if(M == 2){
    cout << (1900 * M + 100 * (N - M)) * 4;
  }
  if(M == 3){
    cout << (1900 * M + 100 * (N - M)) * 8;
  }
  if(M == 4){
    cout << (1900 * M + 100 * (N - M)) * 16;
  }
  if(M == 5){
    cout << (1900 * M + 100 * (N - M)) * 32;
  }
}
      
  
  

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

#define rep(i, n) for(int i = 0; i < (n); i++)
using ll = long long;
constexpr ll INF = 1000000000;

ll gcd(ll a, ll b) {
	if (b == 0)return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}

using namespace std;
int main() {
	string s; cin >> s;

	int n = s.size();

	int a = -1;
	int b = -1;


	int now = 0;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'A') {
			a = i;
			break;
		}
	}

	for (int i = n; i >= 0; i--) {
		if (s[i] == 'Z') {
			b = i;
			break;
		}
	}
	cout << b - a + 1<< endl;
}

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i, n) for(int i = (int)(n); i >= 0; i--)
#define repm(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define repmr(i, m, n) for(int i = (int)(n); i >= (int)(m); i--)
#define all(x) (x).begin(),(x).end()
#define inf 2e9
#define MOD 1000000007

using namespace std;
typedef long long int lli;
typedef long long ll;

int gcd(int x, int y){
  if(y == 0) return x;
  return gcd(y, x % y);
}

int main(){
  int N,X; cin >> N >> X;
  vector<int> x(N); rep(i,N) cin >> x[i];
  x.push_back(X);
  sort(all(x));
  reverse(all(x));

  vector<int> dist(N);
  rep(i,N){
    dist[i] = x[i]-x[i+1];
  }

  int ans = dist[0];
  repm(i,1,N){
    ans = gcd(ans,dist[i]);
  }

  cout << ans << endl;

}


Measured memory_bytes: 1024
#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 x, y;
  cin >> x >> y;
  string ans;
  if (y%2 != 0) ans = "No";
  else {
    if (y <= x*4 && y >= x*2) ans = "Yes";
    else ans = "No";
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <math.h>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
using namespace std;
using ll = long long;
using graph = std::vector<std::vector<long long>>;
int main(){
    ll H,W;
    cin >> H >> W;
    bool isWhite[H][W];
    ll dist[H][W];
    ll whiteCount = 0;
    for(int yi = 0; yi < H; yi++){
        string tmp;
        cin >> tmp;
        for(int xi = 0; xi < W; xi++){
            if(tmp[xi] == '.'){
                isWhite[yi][xi] = true;
                whiteCount++;
            }else{
                isWhite[yi][xi] = false;
            }
            dist[yi][xi] = -1;
        }
    }
    queue<pair<pair<ll,ll>,ll>> s = queue<pair<pair<ll,ll>,ll>>();
    s.push(make_pair(make_pair(0,0),1));
    while(!s.empty()){
        pair<pair<ll,ll>,ll> current = s.front();s.pop();
        if(dist[current.first.first][current.first.second] != -1 || !isWhite[current.first.first][current.first.second]){
            continue;
        }
        dist[current.first.first][current.first.second] = current.second;
        if(current.first.first + 1 < H){
            s.push(make_pair(make_pair(current.first.first + 1,current.first.second),current.second + 1));
        }
        if(current.first.second + 1 < W){
            s.push(make_pair(make_pair(current.first.first,current.first.second + 1),current.second + 1));

        }
        if(current.first.first - 1 >= 0){
            s.push(make_pair(make_pair(current.first.first - 1,current.first.second ),current.second + 1));

        }
        if(current.first.second -1 >= 0){
            s.push(make_pair(make_pair(current.first.first,current.first.second - 1),current.second + 1));

        }
    }
    if(dist[H-1][W-1] == -1){
        cout << -1 << endl;
        return 0;
    }
    cout << whiteCount - dist[H - 1][W - 1] << endl;
}

Measured memory_bytes: 256