akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define vcout(v) rep(i,v.size()) cout << v[i] << " "; cout << endl
#define mcout(m) rep(j,m.size()){vcout(m[j]);}
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
const ll MOD = 1e9 + 7;

void mainsolve(){

	ll n;
	cin >> n;
	vector<P> vv(n);
	rep(i,n){
		ll x,l;
		cin >> x >> l;
		vv[i] = P(x+l, x-l); // 逆にする
	}
	sort(vv.begin(), vv.end());
	ll res = 0;
	ll t = -1e12;
	rep(i,n){
		if(t <= vv[i].second){
			res++;
			t = vv[i].first;
		}
	}
	cout << res << endl;
	return;
}

int main(){
	
	//ll TC;cin>>TC;rep(I,TC){cout<<"case:"<<I+1<<"---"<<endl; // comment out!
		mainsolve();
	//} // comment out!
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll = long long;
const ll N = 200500;
const ll m = (ll)1e9 + 7;
ll n,c[N],dp[N];
vector <ll> pos[N];

ll add(ll a , ll b) {
   return ((a % m) + (b % m)) % m;
}

ll f(ll curr) {
   if (curr > n) return 1;
   ll &sol = dp[curr];
   if (sol != -1) return sol;
   auto it = upper_bound(pos[c[curr]].begin() , pos[c[curr]].end() , curr);
   if (it == pos[c[curr]].end()) {
      sol = f(curr + 1);
   } else {
      if (abs((*it) - curr) == 1) {
         sol = f(curr + 1);
      } else {
         sol = add(f(curr + 1) , f(*it));
      }
   }
   return sol;
}

int main() {
   scanf("%lld" , &n);
   for (ll i = 1 ; i <= n ; i++) {
      scanf("%lld" , &c[i]);
      pos[c[i]].push_back(i);
   }
   memset (dp , -1 , sizeof dp);
   printf("%lld\n" , f(1));
}


Measured memory_bytes: 20608
# -*- coding: utf-8 -*-
from collections import Counter
N, P = map(int, input().split())


def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac

ctr = Counter(primes(P))

ans = 1
for k,v in ctr.items():
    if v >= N:
        ans *= k ** (v//N)

print(ans)


Measured memory_bytes: 3444
#include <stdio.h>

int main(void)
{
	int W, H, x, y, r;
	
	scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
	
	if (y > H || x > W || x + r > W || y + r > H || x < 0 || y < 0){
		printf("No\n");
	}
	else {
		printf("Yes\n");
	}
	return(0);
}

Measured memory_bytes: 584
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(N - 1 + M)]

import sys
sys.setrecursionlimit(200000)

from collections import defaultdict

vs = defaultdict(set)
ws = defaultdict(set)

for a, b in AB:
    vs[a].add(b)
    ws[b].add(a)

#print(vs)
#print(ws)

L = []

cs = [0] * (1 + N)

def visit(n):
    if cs[n] == 1:
        return
    elif cs[n] == 0:
        cs[n] = 1
        for m in vs[n]:
            visit(m)
        cs[n] = 2
        L.append(n)

for n in range(1, N + 1):
    if cs[n] == 0:
        visit(n)

#print(L)

nrank = {}

for r, n in enumerate(L):
    nrank[n] = r

#print(nrank)

for n in range(1, N + 1):
    r = 0
    if ws[n]:
        r = sorted(ws[n], key=lambda x:nrank[x])[0]
    print(r)


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

int main(){
	int N,S;
	while(cin>>N>>S,N){
		int data[101]={0},imo[101]={0},ans=0;
		for(int i=0,A;i<N;i++)cin>>A,data[A]++,imo[A]++;
		for(int i=99;i>=1;i--)imo[i]+=imo[i+1];
		for(int i=1,tmp,tmp2;i<=100;i++){
			tmp=max(1,S-i+1);//魔力iの人が欲しい相手の魔力tmp
			tmp2=imo[tmp];
			if(tmp<=i)tmp2--;
			ans+=(data[i]*tmp2);
		}
		
		
		cout<<ans/2<<endl;
	}
	/*
	1 2 3 4 5 6 7 8 9 10
	1 0 1 0 0 0 0 0 0 1
	3 2 2 1 1 1 1 1 1 1
	
	1:6以上の数=1
	3:4以上の数=1
	10:1以上の数=3(-1自分)
	sum=4
	ans=sum/2=2
	*/
	return 0;
}


Measured memory_bytes: 1160
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, n) for(int i = 1; i <= (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize("Ofast")
using namespace std;
typedef int64_t ll;
typedef long double ld;
const ll INF=(1LL<<60);
const ld pi=acosl(1);
const ll mod = 1000000007;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};

void solve(){
  ll k,s;cin>>k>>s;
  ll ans=0;
  rep(x,k+1)rep(y,k+1){
    ll z=s-x-y;
    if(0<=z and z<=k)ans++;
  }
  cout<<ans<<endl;
}

signed main(){
	ios::sync_with_stdio(false);
  cin.tie(nullptr);cout<<fixed;
  cout<<setprecision(30);
	solve();
}


Measured memory_bytes: 256
#include <iostream>/*{{{*/
#include <bits/stdc++.h>
#define rep(i, x) for(int i = 0; i < (int)(x); i++)
#define reps(i,x) for(int i = 1; i <= (int)(x); i++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define RFOR(i, m, n) for(int i = m;i >= n;i--)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define FILL(x,y) memset(x,y,sizeof(x))
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)
#define debug(x) cerr << __LINE__ << ": " << #x << " -> " << x << '\n'
#define INF 999999999
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};/*}}}*/

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

  int a,b;
  cin >> a >> b;

  int a1,a2,a3,a4,a5;
  int res = 0;
  FOR(i, a, b+1){
    int ci = i;
    a1 = ci%10;
    ci /= 10;
    a2 = ci%10;
    ci /= 10;
    a3 = ci%10;
    ci /= 10;
    a4 = ci%10;
    ci /= 10;
    a5 = ci%10;
    if (a1==a5 and a2==a4) {
      res++;
    }
  }

  cout << res << endl;

  return 0;
}


Measured memory_bytes: 256
{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}

main :: IO ()
main = putStrLn . showResult =<< solve <$> getInput

showResult :: Maybe (Int, Int, Int) -> String
showResult Nothing          = "-1 -1 -1"
showResult (Just (a, b, c)) = show a ++ " " ++ show b ++ " " ++ show c

getInput :: IO (Int, Int)
getInput = do
  [n, y] <- map read . words <$> getLine
  return (n, y)

solve :: (Int, Int) -> Maybe (Int, Int, Int)
solve (n, y) = headMaybe [(a, b, c)
                         | a <- [0 .. n]
                         , b <- [0 .. n]
                         , let c = n - a - b
                         , c >= 0
                         , 10000 * a + 5000 * b + 1000 * c == y
                         ]

headMaybe :: [a] -> Maybe a
headMaybe []     = Nothing
headMaybe (x:xs) = Just x


Measured memory_bytes: 892
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
int N, M, A[101];


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

  cin >> N >> M;
  int sm = 0;
  rep(i, N) {
    cin >> A[i];
    sm+=A[i];
  }
  sort(A, A+N, greater<int>());

  string ans = A[M-1]*4*M>=sm?"Yes":"No";
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 256
#include<map>
#include<bits/stdc++.h>
#include<string>
#include<algorithm>
typedef long long int ll;
using namespace std;
#define MAXN 1e5+5
#define X first
#define Y second
#define MOD 1000000007
#define inf 1e18
#define fr(a,b,c) for(ll a=b;a<c;++a)
#define pb push_back
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ll n,i,j,t;

vector<vector<ll > > adj(MAXN,vector<ll >());
vector<bool > used(MAXN,false);
vector<ll > d(MAXN,0);
vector<ll > in_degree(MAXN,0);
void dfs(ll a){
    used[a]=true;
    for(auto v:adj[a]){
        d[v]=max(d[v],d[a]+1);
        in_degree[v]--;
        if(in_degree[v]==0) dfs(v);
    }
}

int main()
{
    cout<<fixed<<setprecision(20);
    fastio;
    ll n,m,u,v;
    cin>>n>>m;
    for(i=0;i<m;i++){
        cin>>u>>v;
        adj[u].pb(v);
        in_degree[v]++;
    }
    for(i=1;i<=n;i++){
        if(!used[i] && in_degree[i]==0) dfs(i);
    }
    cout<<*max_element(d.begin(),d.end())<<endl;
}


Measured memory_bytes: 10496
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
       Scanner sc = new Scanner(System.in);
        
    while (true) {
        
        int H = sc.nextInt();
        int W = sc.nextInt();
        int i;
        int j;
        
        if(H == 0 && W == 0){  
              break;
        }else{

          for ( i = 0; i < H; i++ ){
   
            for ( j = 0; j < W; j++ ){
                
                if((i+j)%2 == 0){
                      System.out.print("#");//偶数                    

                }else{
                      System.out.print(".");//奇数
                }
            }System.out.println("");
          }System.out.println("");
        }
    }
    }
}
    




Measured memory_bytes: 33120
using System;
using System.Linq;
using System.Collections.Generic;

namespace Aojx
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            List<double[]> posList = new List<double[]>();
            double[] p = { 1, 0 };
            posList.Add(p);

            for (int i = 1; i <= 999; i++)
            {
                double[] pos = posList.Last();

                double rad = Math.Atan(pos[1] / pos[0]);

                if (pos[0] >= 0)
                {
                    rad += Math.PI / 2;
                }
                else
                {
                    rad -= Math.PI / 2;
                }

                double ex = Math.Cos(rad);
                double ey = Math.Sin(rad);

                double[] nextPos =
                    new double[]{ pos[0] + ex, pos[1] + ey };

                posList.Add(nextPos);
            }

            while (true)
            {
                int n = int.Parse(Console.ReadLine());
                if (n == -1)
                {
                    break;
                }

                double[] pos = posList[n - 1];
                Console.WriteLine("{0}\n{1}", pos[0], pos[1]);
            }
        }
    }
}

Measured memory_bytes: 6044
s = input()
s = s[::-1]
n = len(s)

num = [0]*2019
num[0] = 1
number = 0
d = 1

for i in s:
    number += int(i)*d
    num[number%2019] += 1
    d *= 10
    d %= 2019

ans = 0

for i in num:
    ans += i*(i-1)//2

print(ans)

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

int main(){
  long long N,ans,mod;
  ans = 0;
  mod = 1000000007;
  cin >> N;
  long long ans10=1;
  long long ans9=1;
  long long ans8=1;
  for(int i = 1; i <=N; i++){
    ans10 *= 10;
    ans9 *= 9;
    ans8 *= 8;
    ans10%=mod;
    ans9 %=mod;
    ans8 %=mod; 
  }
  
  ans += ans10;
  ans %= mod;
  ans -= ans9;
  ans -= ans9;
  ans %= mod;
  ans += ans8;
  ans %= mod;
  
  if(ans < 0)ans += mod;
  
  cout << ans << endl;
  
  
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define era(t) t.erase(unique(be(t)),t.end())
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
typedef long long ll;
using namespace std;
const ll mod=1000000007,mod9=1000000009;
template <class T>inline T lcm(T a,T b){return (a*b/__gcd(a,b));}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    string s[n+1];
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    int c[n][26];
    memset(c,0,sizeof(c));
    for(int i=0;i<n;i++){
        int maki=s[i].length();
        for(int j=0;j<maki;j++){
            c[i][s[i][j]-'a']++;
        }
    }
    for(int i=1;i<n;i++){
        for(int j=0;j<26;j++){
            c[i][j]=min(c[i][j],c[i-1][j]);
        }
    }
    string ans="";
    for(int i=0;i<26;i++){
        for(int j=0;j<c[n-1][i];j++){
            ans+=(i+'a');
        }
    }
    cout << ans<<endl;
    return 0;
}


Measured memory_bytes: 256
n, k, q = map(int, input().split())
list_point = [int(input()) for i in range(q)]
list_score = [k-q for i in range(n)]

for i in range(q):
    list_score[list_point[i]-1] += 1

for i in range(n):
    if list_score[i] <= 0:
        print("No")
    else:
        print("Yes")

Measured memory_bytes: 11784
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int a,b;
    cin >> a >> b;
    
    if ((a + b)%2 == 0){
        cout << (a + b)/2 << endl;
    }
    
    else cout << (a + b)/2 + 1 << endl;
}


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

#define show(x) cerr << #x << " = " << x << endl ;
#define input_from_file freopen("input.txt","r",stdin)
#define output_to_file freopen("output.txt" , "w",stdout)
#define fastio ios_base::sync_with_stdio(0)
#define endl '\n'

const int N = 1e7 + 10;
long long arr[N];

int main()
{
	 #ifdef LOCAL
        input_from_file;
        output_to_file;
    #endif
	fastio;cin.tie(0);cout.tie(0);
	long long a , b , cnt = 0; cin >> a >> b ;
	if(a == 1 || b == 1)
	{
		cout << 1 ;
		return 0;
	}
	long long m = __gcd(a, b);
	for(long long i = 1 ; i*i <= (m) ; ++i)
	{
		if(m % i == 0)
		{
			arr[cnt++] = i;
			if(i != m/i)
				arr[cnt++] = m/i;
		}
	}
	sort(arr , arr + cnt);
	int ans = cnt;
	for(int i = 0 ; i < cnt - 1 ; ++i)
	{
		for(int j = i + 1 ; j < cnt ; ++j)
		{
			if(arr[i] != -1 && arr[j] != -1 && __gcd(arr[i] , arr[j]) != 1) 
			{
					--ans ;
				arr[j] = -1;
			}
		}
	}
	cout << ans;

	return 0;
}

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

int main()
{

    int x1, x2, x3, x4, y1, y2, y3, y4;

    cin >> x1 >> y1 >> x2 >> y2;

    int Xa = -(y2 - y1);
    int Ya = x2 - x1;

    x3 = x2 + Xa;
    y3 = y2 + Ya;

    int Xb = -(y3 - y2);
    int Yb = x3 - x2;

    x4 = x3 + Xb;
    y4 = y3 + Yb;

    cout << x3<< endl<< y3 << endl << x4 <<endl<< y4 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef vector<pii> vii;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#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 pb push_back
#define mp(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}

//}}}
const ll maxn= 200005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;

		b>>=1;
	}
	return res;
}

ll n,t;
int main()
{
	//IOS;
    string s;
    int white[maxn],black[maxn];
    while(cin>>n>>s)
    {
        memset(black,0,sizeof(black));
        memset(white,0,sizeof(white));
        rep(i,n)
        {
            if(i) {black[i]+=black[i-1];white[i]+=white[i-1];}
            if(s[i]=='#') black[i]++;
            else white[i]++;
        }
        int minchange=white[n-1];
        rep(i,n)
        {
            minchange=min(minchange,black[i]+white[n-1]-white[i]);
        }
        cout<<minchange<<"\n";
    }
	return 0;
}

Measured memory_bytes: 2180
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

int main() {
    int n;
    cin >> n;

    int x[n][3];
    rep(i, n) {
        rep(j, 3) {
            int X;
            cin >> X;
            x[i][j] = X;
        }
    }

    int dp[n+1][3];
    rep(i, n+1) {
        rep(j, 3) {
            dp[i][j] = 0;
        }
    }

    rep(i, n) {
        rep(j, 3) {
            rep(k, 3) {
                if(k == j) {
                    continue;
                }
                dp[i+1][j] = max( dp[i+1][j], dp[i][k] + x[i][j] );
            }
        }
    }

    int ans = 0;
    rep(j, 3) {
        ans = max(ans, dp[n][j]);
    }

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

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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define MP make_pair
ll MOD = 1e9+7;
//ll MOD = 998244353;
ll INF = 1e18;
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x,ll y,ll z){if(x)cout<<y<<endl;else cout<<z<<endl;}
void anss(bool x,string y,string z){if(x)cout<<y<<endl;else cout<<z<<endl;}   
ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;}

int main(){
  ll i,j,o;
  ll res=0,res1=0,res2=INF,buf=0,buf1=0,buf2=0,buf3=0,buf4=0;
  bool judge = true;
  ll h,w,n;cin>>h>>w>>n;
  vector<ll>a(n),b(10001);
  for(i=0;i<n;i++)cin>>a[i];

  for(i=0;i<n;i++){
    for(j=0;j<a[i];j++,buf++){
      b[buf]=i;
    }
  }

  ll m[h][w];
  for(i=0;i<h;i++){
    if(i%2==0){
      for(j=0;j<w;j++){
        m[i][j]=b[i*w+j]+1;
      }
    }
    else{
      for(j=w-1;j>=0;j--){
        m[i][j]=b[i*w+w-j-1]+1;
      }
    }
  }

  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      cout<<m[i][j]<<" ";
    }
    cout<<endl;
  }
  

  return 0;
}

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

int main() {
  int n, m;
  cin >> n >> m;
  vi a(m);
  vector<vi> c(m);
  rep(i, m) {
    int b;
    cin >> a[i] >> b;
    rep(j, b) {
      int cc;
      cin >> cc;
      cc--;
      c[i].push_back(cc);
    }
  }
  int b = 1 << n;
  int dp[b];
  rep(j, 1 << n) dp[j] = 1e9;
  dp[0] = 0;
  rep(i, m) for(int j = b - 1; j >= 0; j--) {
    if(dp[j] == 1e9) continue;
    int nj = j;
    for(int v : c[i]) nj |= (1 << v);
    dp[nj] = min(dp[nj], dp[j] + a[i]);
  }
  cout << (dp[b - 1] == 1e9 ? -1 : dp[b - 1]) << endl;
}

Measured memory_bytes: 384
m,d = map(int,input().split())
f = []
d1,d10,cout = 0,0,0
for i in range(m):
  for j in range(d):
    if j+1 >= 10:
      f = list(str(j+1))
      d10 = int(f[0])
      d1 = int(f[1])
    if d1 >=2 and d10 >= 2:
      if d1*d10 == i+1:
        cout += 1
  d10,d1 = 0,0
print(cout)

Measured memory_bytes: 3064
#include<stdio.h>

bool binarySearch(int A[], int left, int right, int t) {
  int m = (left + right) / 2;
  if ( A[m] == t ) return true;
  else if ( left == right ) return false;
  return A[m] > t ? binarySearch(A, left, m, t) : binarySearch(A, m + 1, right, t);
}

int main() {
  int n, A[100000], cnt = 0;
  scanf("%d", &n);

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

  int m, t;
  scanf("%d", &m);
  for ( int i = 0; i < m; i++ ) {
    scanf("%d", &t);
    if (binarySearch(A, 0, n, t)) cnt++;
  }

  printf("%d\n", cnt);
  return 0;
}


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

vector <char> stk;

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

	string str;
	cin >> str;

	for(char x : str)
	{
		switch(x)
		{
		case 'S':
			stk.push_back(x);
			break;
		case 'T':

			if(stk.empty() || stk.back() == 'T')
				stk.push_back(x);
			else
				stk.pop_back();
			break;
		}
	}

	cout << stk.size() << endl ;

}


Measured memory_bytes: 788
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int sum = 1;
        for (int i = 1; i <= n; i++) {
            sum = Math.min(sum * 2, sum + k);
        }
        System.out.println(sum);
    }
}

Measured memory_bytes: 35828
#ifdef _MSC_VER
#include "stdc++.h"
#endif
#ifdef __GNUC__
#include<bits/stdc++.h>
#endif
using namespace std;

using ll = long long;

//vector
using vi = vector<int>;
using vii = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;

//constant
const double EPS = 1e-10;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, s, e) for (ll i = s; i < e; i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(), (x).rend()

//debug
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;

// vector
//template<typename T> vector<vector<T>> vv(ll H, ll W, T v) { return vector<vector<T>> vec(H, vector<T>(W, v)); }

// view vector
template<typename T> void view(T e) { cout << e << endl; }
template<typename T> void view(const vector<T>& v) { for (const auto& e : v) { cout << e << " "; } cout << endl; }
template<typename T> void view(const vector<vector<T> >& vv) { for (const auto& v : vv) { view(v); } }

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




// ***************************************

struct Eratos {
    vector<int> primes;
    vector<bool> isprime;
    vector<int> mebius;
    vector<int> min_factor;
 
    Eratos(int MAX) : primes(),
                      isprime(MAX+1, true),
                      mebius(MAX+1, 1),
                      min_factor(MAX+1, -1) {
        isprime[0] = isprime[1] = false;
        min_factor[0] = 0, min_factor[1] = 1;
        for (int i = 2; i <= MAX; ++i) {
            if (!isprime[i]) continue;
            primes.push_back(i);
            mebius[i] = -1;
            min_factor[i] = i;
            for (int j = i*2; j <= MAX; j += i) {
                isprime[j] = false;
                if ((j / i) % i == 0) mebius[j] = 0;
                else mebius[j] = -mebius[j];
                if (min_factor[j] == -1) min_factor[j] = i;
            }
        }
    }
 
    // prime factorization
    vector<pair<int,int>> prime_factors(int n) {
        vector<pair<int,int> > res;
        while (n != 1) {
            int prime = min_factor[n];
            int exp = 0;
            while (min_factor[n] == prime) {
                ++exp;
                n /= prime;
            }
            res.push_back(make_pair(prime, exp));
        }
        return res;
    }
 
    int func(int n) {
        int res = 1;
        while (n != 1) {
            int prime = min_factor[n];
            int exp = 0;
            while (min_factor[n] == prime) {
                ++exp;
                n /= prime;
            }
            res *= exp + 1;
        }
        return res;
    }
};


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

    Eratos er = Eratos(N + 1);
    ll ans = 0;
    FOR(i, 1, N + 1){
        ans += i * er.func(i);
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 86704
#include <stdio.h>
   
int main(void){   
    int n, m;
    int i, j;
    int A[100][100];
    int b[100], c[100];
    
    scanf("%d %d", &n, &m);
    for(i=0; i<n; i++){
        for(j=0; j<m; j++) scanf("%d", &A[i][j]);
    }
    for(i=0; i<m; i++) scanf("%d", &b[i]);
    
    for(i=0; i<n; i++){
        c[i] = 0;
        for(j=0; j<m; j++) c[i] += A[i][j] * b[j];
    }
     for(i=0; i<n; i++) printf("%d\n", c[i]);
    return 0;
}


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

int main()
{
    string str1, str2;
    cin >> str1 >> str2;

    if(str2.length() != str1.length() + 1)
    {
        cout<<"No"<<endl;
        return 0;
    }
    int i = 0;
    for(i = 0; i < str1.length(); i++)
    {
        if(str1[i] != str2[i])
        {
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;

    return 0;
}

Measured memory_bytes: 3624
#include<stdio.h>
#include<stdlib.h>

int
main(int argc, char *argv[])
{
        char in;

        while (in = getc(stdin), in != '\n') {
                if ('a' <= in && in <= 'z')
                        in = in - 'a' + 'A';
                else if ('A' <= in && in <= 'Z')
                        in = in - 'A' + 'a';
                putc((int)in, stdout);
        }
        putc((int)'\n', stdout);

        return 0;
}

Measured memory_bytes: 524
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1<<30;
int main(){
	int n;
	cin>>n;
	vp in(n);
	rep(i,n)cin>>in[i].first>>in[i].second;
	sort(all(in));
	int mi=inf;
	rep(i,n)loop(j,max(0,i-5),min(n,i+5))if(i!=j)
		mi=min(mi,(in[i].first-in[j].first)*(in[i].first-in[j].first)+
			(in[i].second-in[j].second)*(in[i].second-in[j].second));
	cout<<mi<<endl;
}

Measured memory_bytes: 4964
#include<bits/stdc++.h>
#define LL long long int
#define INF 734858
using namespace std;
int main(void)
{
	LL b,ka,t,w,ki,y,m,d,sum,cnt,mon,day,year;
	LL i,j,k;
	LL maya[5]={144000,7200,360,20,1};
	LL month[2][12]={
					{31,28,31,30,31,30,31,31,30,31,30,31},
					{31,29,31,30,31,30,31,31,30,31,30,31}
					};
	char s[100];
	while(1) {
		cin>>s;
		if(s[0]=='#') break;
		cnt=0;
		for(i=0;i<strlen(s);i++) {
			if(s[i]=='.') cnt++;
		}
		if(cnt==2) { //?\?????????????
			sum=0;
			string sum2;
			sum2=s[0];
			for(i=1;i<strlen(s);i++) {
				if(s[i]=='.') break;
				else sum2+=s[i];
			}
			int mx;
			mx=atoi(sum2.c_str());
			for(i=1;i<mx;i++) {
				if(i%4==0&&i%100!=0||i%400==0) sum+=366;
				else sum+=365;
			}
			int f=0;
			for(i=0;i<strlen(s);i++) {
				if(s[i]=='.'&&s[i+2]=='.') {
					sum2=s[i+1];
					if(f==0) mon=atoi(sum2.c_str());
					else day=atoi(sum2.c_str());
					f=1;
				}
				else if(s[i]=='.'&&s[i+2]!='.') {
					sum2=s[i+1];
					sum2+=s[i+2];
					if(f==0) mon=atoi(sum2.c_str());
					else day=atoi(sum2.c_str());
					f=1;
				}
			}
			int test=0;
			for(i=0;i<mon-1;i++) {
				if(mx%4==0&&mx%100!=0||mx%400==0) sum+=month[1][i];
				else sum+=month[0][i];
			}
			sum+=day,sum-=INF;
			b=sum/maya[0],sum=sum%maya[0];
			ka=sum/maya[1],sum=sum%maya[1];
			t=sum/maya[2],sum=sum%maya[2];
			w=sum/maya[3],ki=sum%maya[3];
			cout<<b%13<<"."<<ka%20<<"."<<t%20<<"."<<w%18<<"."<<ki%20<<endl;
		}
		else { //??????????\????
			sum=0;
			LL swi=1,x;
			string sum3;
			if(s[1]=='.') sum3=s[0],sum+=atoi(sum3.c_str())*maya[0];
			else if(s[1]!='.') sum3=s[0],sum3+=s[1],sum+=atoi(sum3.c_str())*maya[0];
			for(i=0;i<strlen(s);i++) {
				if(s[i]=='.'&&s[i+2]=='.') {
					sum3=s[i+1];
					sum+=atoi(sum3.c_str())*maya[swi];
					swi++;					
				}
				else if(s[i]=='.'&&s[i+2]!='.') {
					sum3=s[i+1],sum3+=s[i+2];
					sum+=atoi(sum3.c_str())*maya[swi];	
					swi++;		
				}
			}
			int zan=10;
			if(sum<11) {
				cout<<"2012.12."<<sum+21<<endl;
			}
			else {
				sum-=10;
				LL suu=2013;
				while(1) {
					if(suu%4==0&&suu%100!=0||suu%400==0) {
						if(sum>366) {
							sum-=366;
						}
						else if(sum==366) {
							sum-=366;
							mon=12,day=31;
						}
						else {
							mon=1;
							for(i=0;i<12;i++) {
								if(sum>=month[1][i]&&mon-1>=i) {
									if(sum-month[1][i]==0) break;
									sum-=month[1][i];
									mon++;
								}
							}
							day=sum;
							sum=0;
						}
					}
					else {
						if(sum>365) {
							sum-=365;
						}
						else if(sum==365) {
							sum-=365;
							mon=12,day=31;
						}
						else {
							mon=1;
							for(i=0;i<12;i++) {
								if(sum>=month[0][i]&&mon-1>=i) {
									if(sum-month[0][i]==0) break;
									sum-=month[0][i];
									mon++;
								}
							}
							day=sum;
							sum=0;
						}
					}
					if(sum==0) break;
					suu++;
				}
				cout<<suu<<"."<<mon<<"."<<day<<endl;
			}
		}
	}
}
	

Measured memory_bytes: 3164
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void swap_int(int *x, int *y) {int temp;temp = *x;*x = *y;*y = temp;}
void swap_char(char *x, char *y) {char temp;temp = *x;*x = *y;*y = temp;}
int max(int x, int y) { return x > y ? x : y; }
int min(int x, int y) { return x > y ? y : x; }

int main(void){
    int n,k;

    scanf("%d %d",&n,&k);
    if(k==1){
        printf("0\n");
    }else{
        printf("%d\n",n-k);
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>

#ifdef _MSC_VER
#include <Windows.h>
#else
#include <unistd.h>
#endif

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD=(LL)1e9+7;
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

#define INF 1LL << 50

const int MAX_V=2e5+1;

struct edge{int to,cost;};
typedef pair<int,int> P;//firstは最短距離,secondは頂点番号

int V;
vector<edge> G[MAX_V];
int d[MAX_V],prv[MAX_V];

void dijkstra(int s){
    priority_queue<P,vector<P>,greater<P> > que;
    fill(d,d+V,INT_MAX);
    fill(prv,prv+V,-1);
    d[s]=0;
    que.push(P(0,s));
    
    while(!que.empty()){
        P p=que.top();que.pop();//仮の最短距離が短い順に取り出す
        int v=p.second;
        if(d[v]<p.first)continue;
        REP(i,G[v].size()){
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                prv[e.to]=v;
                que.push(P(d[e.to],e.to));//仮の最短距離と頂点の組を更新が行われる度に追加していく
            }
        }
    }
}

int main(){
    int M;
    cin>>V>>M;
    REP(i,M){
        int a,b;
        cin>>a>>b;
        a--;b--;
        edge e={b,1};
        edge e2={a,1};
        G[a].PB(e);
        G[b].PB(e2);
    }
    dijkstra(0);
    if(d[V-1]==2){
        cout<<"POSSIBLE"<<endl;
    }else{
        cout<<"IMPOSSIBLE"<<endl;
    }
    return 0;
}

Measured memory_bytes: 15848
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000007;
 
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  string S, T;
  cin >> S >> T;
  int N = S.size(), M = T.size();
  bool ans = false;
  for(int i=N-1;i>=0;i--){
    if(ans) continue;
    for(int j=M-1;j>=0;j--){
      if(j == 0){
        if(S[i-(M-1-j)] == T[j] || S[i-(M-1-j)] == '?'){
          ans = true;
          for(int j=M-1;j>=0;j--){
            S[i-(M-1-j)] = T[j];
          }
        }
      }
      else if(S[i-(M-1-j)] == T[j] || S[i-(M-1-j)] == '?'){
        continue;
      } 
      else{
        break;
      }
    }
  }
  if(ans){
    for(int i=0;i<N;i++){
      if(S[i] == '?'){
        S[i] = 'a';
      }
    }
  }
  if(ans) cout << S << endl;
  else cout << "UNRESTORABLE" << endl;
}

Measured memory_bytes: 256
(n, m, q) = map(int, input().split())
num_sets = [tuple(map(int, input().split())) for _ in range(q)]

a_opt = []
for ni in range(n):
    a_opt_next = []
    if len(a_opt) == 0:
        for mi in range(1, m + 1):
            a_next = [mi]
            a_opt_next.append(a_next)
    else:
        for a in a_opt:
            for mi in range(a[-1], m + 1):
                a_next = a + [mi]
                a_opt_next.append(a_next)
    a_opt = a_opt_next[:]

ans = 0
for a in a_opt:
    sumd = 0
    for num_set in num_sets:
        if a[num_set[1] - 1] - a[num_set[0] - 1] == num_set[2]:
            sumd += num_set[3]
    ans = max(ans, sumd)

print(ans)


Measured memory_bytes: 31168
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
//#のマスのみを通って、最短距離で左上から右下のマスに移動できるかを調べる
//常に右または下に動く時、最短距離で右下まで行ける　つまり#の個数が最短距離に一致
int main() {
 int H,W;
 cin >> H >> W;
 vector<vector<char>> maze(H, vector<char>(W));
 for(int i = 0;i<H;i++){
     for(int j = 0;j<W;j++){
         cin >> maze[i][j];
     }
 }
 int d = 0;//#の個数がH+W-1であれば最短移動している
 for(int i = 0;i<H;i++){
     for(int j = 0;j<W;j++){
         if(maze[i][j] == '#') d++;
     }
 }

if(d == H+W-1) cout << "Possible" <<endl;
else cout << "Impossible" <<endl;
 
}

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

int main() {
    int   N;
    cin >> N;
    int K;
    cin >> K;
    vector<int> H(N);
    int allow = 0;

    for (int i = 0; i < N; i++) {
      cin >> H.at(i);
      if (H.at(i) >= K){
        allow++;
      }
    }

    cout << allow << endl;

}

Measured memory_bytes: 640
#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
 
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef pair<int, int> pi;


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

  int ans = h/a;
  if (h % a >0) ans++;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		double x1 = s.nextDouble();
		double y1 = s.nextDouble();
		double x2 = s.nextDouble();
		double y2 = s.nextDouble();
		System.out.println(Math.hypot(x2 - x1, y2 - y1));
	}
}

Measured memory_bytes: 18320
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

#include <bits/stdc++.h>

#define F first
#define S second
#define _sz(x) (int)x.size()

#define pb push_back

using namespace std ;
using ll = long long ;
using ld = long double ;
using pii = pair <int , int> ;

const int N = 1e5 + 20 ;
int n , m , a[N] ;
int last[N] , ans ;
bool vis[N] ;
vector <int> g[N] , v1 , v2 ;

void dfs (int v) {
	vis[v] = 1 ;
	v1.pb(v) ;
	v2.pb(a[v]) ;

	for (int u : g[v])
		if (!vis[u]) dfs(u) ;
}

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

	cin >> n >> m ;
	for (int i = 0 ; i < n ; i ++) cin >> a[i] , a[i] -- ;

	for (int i = 0 , u , v ; i < m ; i ++) {
		cin >> u >> v ;
		u -- , v -- ;

		g[u].pb(v) ;
		g[v].pb(u) ;
	}

	for (int i = 0 ; i < n ; i ++) {
		if (vis[i]) continue ;
		
		v1.clear() ;
		v2.clear() ;

		dfs(i) ;

		for (int x : v1) last[x] = i + 1 ;
		for (int x : v2) if (last[x] == i + 1) ans ++ ;
	}

	cout << ans << '\n' ;
}


Measured memory_bytes: 10532
#include <iostream>                                                                                                   
  
  int main(){
     int N;
     std::cin >> N;
     int a[N];
     for(int i=0; i<N; ++i)
        std::cin >> a[i];
  
     long long ans = 0;
     for(int i=0; i<N; ++i){
        int count = 0;
        while(a[i]%2==0){
           a[i] /= 2;
           ++count;
        }
        ans += count;
     }
     std::cout << ans << std::endl;
     return 0;
 }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  V< set<int> > g(n);
  for (int i = 0; i < n - 1; ++i) {
    int u, v; cin >> u >> v;
    g[u].insert(v);
    g[v].insert(u);
  }
  for (int i = 0; i < n; ++i) if ((int)g[i].size() == 2) {
    int u = *begin(g[i]), v = *next(begin(g[i]));
    set<int>().swap(g[i]);
    g[u].erase(i);
    g[v].erase(i);
    g[u].insert(v);
    g[v].insert(u);
  }
  int c = count_if(begin(g), end(g), [](const auto& se) { return (int)se.size() >= 3; });
  if (!c) return cout << 1 << '\n', 0;
  int res = count_if(begin(g), end(g), [](const auto& se) { return (int)se.size() == 1; });
  for (const auto& se : g) if ((int)se.size() >= 3) {
    bool be = false;
    for (int e : se) if ((int)g[e].size() == 1) {
      be = true;
      break;
    }
    res -= be;
  }
  cout << res << '\n';
}

Measured memory_bytes: 14336
K = int(input())

def gcd_(a, b):
    if a < b:  a, b = b, a
    if b == 0:  return a
    return gcd_(b, a % b)

def gcd(l):
    ans = l[0]
    for i in l:  ans = gcd_(ans, i)
    return ans

ans = 0

for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            ans += gcd([i, j, k])

print(int(ans))

Measured memory_bytes: 72688
// Example program
#include <iostream>
#include <string>

using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n],i,k,max;
    k=0;
    for(i=0;i<n;i++)
    cin>>a[i];
    max=0;
    for(i=0;i<n-1;i++)
    {
        if(a[i]>=a[i+1])
        k++;
        else
        k=0;
        if(k>max)
        max=k;
    }
    
    cout<<max<<endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PQ = priority_queue<int, vector<int>, greater<int>>;

vector<vector<int>> G;
vector<int> color;
vector<PQ> ques;
ll ans;

int N, M;
vector<int> a;

void dfs(int v, int c) {
  color[v] = c;
  ques[c].push(a[v]);
  for (auto x : G[v]) {
    if (color[x] == c) continue;
    if (color[x] == -1) dfs(x, c);
  }
  return;
}

int main() {
  cin >> N >> M;
  a.resize(N); for (int i = 0; i < N; i++) cin >> a[i];
  G.resize(N);
  for (int i = 0; i < M; i++) {
    int x, y; cin >> x >> y;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  if (N - M - 1) {
    if (N < 2 * (N - M - 1)) {
      cout << "Impossible" << endl;
      return 0;
    }
    int cnt {};
    color.assign(N, -1);
    ques.resize(N);
    for (int i = 0; i < N; i++) {
      if (color[i] == -1) {
        dfs(i, cnt);
        ans += ques[cnt].top(); ques[cnt].pop();
        cnt++;
      }
    }
    vector<int> v;
    ques.resize(cnt);
    for (int i = 0; i < cnt; i++) {
      while (!ques[i].empty()) {
        v.push_back(ques[i].top());
        ques[i].pop();
      }
    }
    sort(begin(v), end(v));
    for (int i = 0; i < 2 * (N - M - 1) - cnt; i++) ans += v[i];
  }
  cout << ans << endl;
  return 0;
}


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

// typedef
// -----------------------------------------------------------------------------
typedef long long ll;
typedef long double ld;

// container util
// -----------------------------------------------------------------------------
#define ALL(c)  (c).begin(),(c).end()
#define SZ(c) ((ll)(c).size())
#define MAX(c) *max_element(ALL(c))
#define MIN(c) *min_element(ALL(c))
#define SORT(c) sort((c).begin(),(c).end())

// repetition
// -----------------------------------------------------------------------------
#define FOR(i, a, b) for(ll i= (a); i < (ll)(b); ++i)
#define REP(i, n) FOR(i, 0, n)

// constant
// -----------------------------------------------------------------------------
const ll INF = 1e10;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = acos(-1.0);

// debug
// -----------------------------------------------------------------------------
#define DUMP(x)  cerr << #x << " = " << (x) << endl


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    ll N, M, K; cin >> N >> M >> K;
    vector<ll> A(N + 1, 0);
    FOR(i, 1, N + 1) {
        cin >> A[i];
        A[i] += A[i - 1];
    }
    vector<ll> B(M + 1, 0);
    ll j = 0;
    FOR(i, 1, M + 1) {
        cin >> B[i];
        B[i] += B[i - 1];
        if (B[i] <= K) {
            j = i;
        }
    }
    ll ans = 0;
    REP(i, N + 1) {
        if(A[i] > K) {
            break;
        }
        while(K - A[i] < B[j]) {
            j--;
        }
        ans = max(ans, i + j);
    }
    cout << ans << "\n";
}

Measured memory_bytes: 6364
#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>;

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

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

int main() {
  string s;
  cin >> s;
  int sum = 0;
  rep(i, s.length()) {
    sum += s[i] - '0';
  }
  if (sum % 9 == 0)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3712
#include <stdio.h>

void merge( int A[], int left, int mid, int right );
void mergeSort( int A[], int left, int right );

int A[500000];
int count = 0;

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

  mergeSort( A, 0, n);

  for( i = 0; i < n; i++){
    if(i > 0)printf(" ");
    printf("%d",A[i]);
  }
  printf("\n");
  printf("%d\n",count);
  
  return 0;
  
}

void mergeSort( int A[], int left, int right )
{
  int mid;

  if( ( left + 1 ) < right ){
    mid = ( left + right )/2;
    mergeSort( A, left, mid);
    mergeSort( A, mid, right);
    merge( A, left, mid, right);

  }

}


void merge( int A[], int left, int mid, int right )
{
  int i,n1,n2;
  int j;
  int k;
  int L[mid-left],R[right-mid];

  n1 = mid - left;
  n2 = right - mid;

  for( i = 0; i < n1; i++){
    L[i] = A[left + i];  
  }
  
  for( i = 0; i < n2; i++){
    R[i] = A[mid + i];    
  }

  L[n1] = R[n2] = 1000000000;
  i = 0;
  j = 0;

  for( k = left; k < right; k++){

    if( L[i] <= R[j]){
      A[k] = L[i];
      i = i + 1;
    }    
    else{
      A[k] = R[j];
      j = j + 1;
    }
    count++;
  }
}





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

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

int dfs(int d, int a, int b, int c){
    if(d == N){
        if(min({a, b, c}) > 0){
            return abs(a-A)+abs(b-B)+abs(c-C)-30;
        }else{
            return 10000000;   
        }
    }else{
        return min({
            dfs(d+1, a+l[d], b, c)+10,
            dfs(d+1, a, b+l[d], c)+10,
            dfs(d+1, a, b, c+l[d])+10, 
            dfs(d+1, a, b, c)
            });
    }
}

int main(){
    cin >> N >> A >> B >> C;

    l.resize(N);
    for(int i = 0; i < N; ++i){
        cin >> l[i];
    }

    cout << dfs(0, 0, 0, 0) << endl;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	//予備
	x := iScan()
	if x < 0 {
		x = x * (-1)
	}
	k := iScan()
	d := iScan()
	a := x / d
	b := x % d
	if a > k {
		fmt.Println(x - d*k)
		return
	}
	if (k-a)%2 == 0 {
		fmt.Println(b)
	} else {
		fmt.Println(d - b)
	}
}

Measured memory_bytes: 1776
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <queue>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ldb = long double;

#define pb emplace_back
#define forn(i, x, n) for(auto i = (int)x; i < (int)n; ++i)

#define int long long

struct init {
    init() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        cout << fixed << setprecision(10);
    }

    ~init() {
        cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC << "s.\n";
    }
} init;

const int N = 100500 * 2, MOD = 1000 * 1000 * 1000 + 7;
const ldb EPS = 5e-12, HALF = 0.5;

int a[N];

signed main() {
    int n;
    cin >> n;
    int sum = 0;

    forn(i, 0, n) {
        cin >> a[i];
        a[i] -= i + 1;
        sum += a[i];
    }

    int l = -1e9 - 1, r = 1e9 + 1;
    int mn = 1e18;
    while (r - l > 1) {
        int mid = (r + l) / 2;
        int sum1 = 0, sum2 = 0;
        forn(i, 0, n) {
            sum1 += abs(a[i] - mid);
            sum2 += abs(a[i] - mid - 1);
        }

        mn = min(mn, min(sum1, sum2));

        if (sum1 < sum2) {
            r = mid;
        } else {
            l = mid;
        }
    }
    cout << mn;
}


Measured memory_bytes: 1792