akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;
using i64 = int64_t;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep2(i, x, n) for(int i=x;i<n;++i)

int main()
{   
    int a,b;
    string s;
    cin >> a >> b >> s;
    int n = a+b+1;

    bool is_ok = true;
    rep(i,n)
    {
        if(i==a)
            is_ok &= (s.substr(i,1)=="-");
        else
            is_ok &= (isdigit(s.substr(i,1).c_str()[0]));
    }

    cout << (is_ok ? "Yes" : "No") << endl;
    return 0;
}

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

const char NL = '\n';
const int MOD = 1e9 + 7;

void solve()
{
    int n; cin >> n;
    string st;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        char c; cin >> c; st += c;
    }
    int left = 0, right = st.size() - 1;
    while (left < right) {
        if (st[left] == 'R') ++left;
        else if (st[right] == 'W') --right;
        else {
            swap(st[left], st[right]);
            ++ans;
        }
    }
    cout << ans << NL;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

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


int main() {
    int N, M;
    cin >> N >> M;
    int ans = N * (N-1) / 2 + M * (M-1) /2;
    cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string H,W;
  cin >> H >> W;
  
  if (H.at(0) == W.at(2) && H.at(1) == W.at(1) &&H.at(2) == W.at(0)){
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}
  
  

Measured memory_bytes: 3484
N, L = map(int, input().split())


aji = [L + i for i in range(N)]

aji_abs = list(map(abs, aji))
min_tmp = float('inf')
indx = -1
for i, x in enumerate(aji_abs):
    if x < min_tmp:
        min_tmp = x
        indx = i

ans = sum(aji)
ans -= (aji[indx])

print(ans)

Measured memory_bytes: 38384
#include<iostream>
using namespace std;
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cmath>
#define int long long int
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,answer=0,i,j,k;
	cin>>n;
	int arr[n];
	for(j=0;j<n;j++)
	   cin>>arr[j];
    for(i=0;i<n;i++)
    {
		for(j=i+1;j<n;j++)
		{
			for(k=j+1;k<n;k++)
			{
				
				int val1=arr[i];
				int val2=arr[j];
				int val3=arr[k];
				if(val1==val2||val2==val3||val1==val3)
				   continue;
				if(val3<val1+val2&&val2<val1+val3&&val1<val2+val3)
				   answer++;
			}
		}
	}
	cout<<answer<<endl;
}


Measured memory_bytes: 3644
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define Nmax 200010
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define RFOR(i,a,b) for(long long i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<P> Graph;
 
int main() {//答え聞いた後版
	int N;
	cin >> N;
	ll A[Nmax]={};
	REP(i,N){
		cin >> A[i];
		A[i]-=i+1;
	}
  	sort(A,A+N);
	ll b=A[(N-1)/2];//med
	ll mina=0;//ans
	REP(i,N) mina+=abs(A[i]-b);

	cout << mina << endl;
	return 0;
}

Measured memory_bytes: 1792
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
int n;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    string s;
    cin >> s;
    int bal = 0;
    n = s.size();
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'g') bal--;
        else bal++;
    }
    int our_bal = (n % 2 == 0 ? 0 : -1);
    cout << (our_bal - bal) / 2;
    return 0;
}

Measured memory_bytes: 512
package main

import (
	"fmt"
	"strings"
)

func connectionAndDisconnection(s string, k int) int {

	// all the characters in S are the same pattern
	m := make(map[rune]int, 26)

	for _, c := range s {
		m[c]++
	}
	if len(m) == 1 {
		return (len(s) * k) / 2
	}

	// If these characters are the same pattern
	r := []rune(s)
	cost := 0
	if s[0] == s[len(s)-1] {
		for i := 1; i < len(r); i++ {
			if r[i-1] == r[i] {
				cost++
				r[i] = '#'
			}
		}
		l := string(s[0])
		head := len(s) - len(strings.TrimLeft(s, l))
		tail := len(s) - len(strings.TrimRight(s, l))
		return cost*k - (head/2+tail/2-(head+tail)/2)*(k-1)

	}
	// If the first and last characters of S are different pattern.
	for i := 1; i < len(r); i++ {
		if r[i-1] == r[i] {
			cost++
			r[i] = '#'
		}
	}
	return cost * k
}

func main() {
	var s string
	var k int
	fmt.Scan(&s)
	fmt.Scan(&k)
	fmt.Println(connectionAndDisconnection(s, k))
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;

int main()
{
    string N;
    cin >> N;
    if (N.at(0) == N.at(2))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;
typedef long double ld;

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    int h, n;
    cin >> h >> n;
    vector<vector<int> > dp(n + 1, vector<int>(h + 1, Inf));
    dp[0][0] = 0;
    rep (i, n) {
        int a, b;
        cin >> a >> b;
        rep (j, h + 1) {
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
            int t = min(h, j + a);
            dp[i + 1][t] = min(dp[i + 1][t], dp[i + 1][j] + b);
        }
    }
    int res = Inf;
    rep (i, n + 1) res = min(res, dp[i][h]);
    cout << res << endl;
    
    return 0;
}



Measured memory_bytes: 39424
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <array>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define endl '\n'
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

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

struct Trie{
    struct Node{
        int c;
        array<int,26> nxt;
        array<int,26> cnt;
        int sz;

        Node(int c):c(c),sz(0){
            nxt.fill(-1);
            cnt.fill(0);
        }
    };
    vector<Node> nodes;

    Trie(){nodes.emplace_back(-1);}

    void add(const string& s){
        int pos=0;
        for(char c:s){
            int ci=c-'a';

            int npos=nodes[pos].nxt[ci];
            if(npos==-1){
                npos=nodes.size();
                nodes[pos].nxt[ci]=npos;
                nodes.emplace_back(ci);
            }
            pos=npos;
        }
        ++nodes[pos].sz;
    }

    int find(const string& s) const{
        int pos=0;
        for(char c:s){
            int ci=c-'a';
            pos=nodes[pos].nxt[ci];
        }
        return pos;
    }
    
    void fillcnt(){
        for(int pos=(int)nodes.size()-1;pos>=0;--pos){
            auto& node=nodes[pos];
            
            rep(c,26){
                int npos=node.nxt[c];
                if(npos==-1) continue;
                
                const auto& cnode = nodes[npos];
                node.sz+=cnode.sz;
                rep(d,26){
                    node.cnt[d]+=cnode.cnt[d];
                }
            }
            if(node.c!=-1) node.cnt[node.c]=node.sz;
        }
    }
};

int main(){
    int n;
    cin >> n;
    vector<string> ss(n);
    rep(i,n){
        cin >> ss[i];
        reverse(ss[i].begin(),ss[i].end());
    }
    Trie trie;
    for(const auto& s:ss) trie.add(s);
    trie.fillcnt();
    ll ans=0;
    for(auto s:ss){
        ll last=s.back()-'a';
        s.pop_back();
        
        int pos=trie.find(s);
        rep(ci,26){
            int npos=trie.nodes[pos].nxt[ci];
            if(npos==-1) continue;
            ans+=trie.nodes[npos].cnt[last];
            if(ci==last) --ans;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 227868
# author:  Taichicchi
# created: 12.09.2020 18:05:06

import sys

N, M = map(int, input().split())

ls = []

for i in range(N):
    ls.append(list(map(int, input().split())))

ls.sort(key=lambda x: x[0])

ans = 0

for l in ls:
    if l[1] <= M:
        M -= l[1]
        ans += l[0] * l[1]
    else:
        ans += l[0] * M
        break


print(ans)


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

int main() {
    string s,t;
    cin >> s >> t;
    int size = s.size();
    vector<int> cacheS(26),cacheT(26);
    bool pattern_match = true;
    int sNum,tNum;
    for(int i = 0; i < size; i++)
    {
        sNum = s.at(i) - 'a';
        tNum = t.at(i) - 'a';
        if (cacheS.at(sNum) != cacheT.at(tNum)) {
            pattern_match = false;
            break;
        }
        cacheS.at(sNum) = i;
        cacheT.at(tNum) = i;
    }

    string ans;
    if(pattern_match) ans = "Yes";
    else ans = "No";

    cout << ans << endl;
}

Measured memory_bytes: 776
#include <bits/stdc++.h>
#include <iomanip>
#define ll long long
using namespace std;

int main() {
  ll N, X, Y;
  cin >> N >> X >> Y;
  vector<ll> a(N + 1, 0);
  for(ll i = 1; i < N; i++) {
    for(ll j = i + 1; j < N + 1; j++) {
      if(j <= X) a.at(j - i)++;
      else if(i >= Y) a.at(j - i)++;
      else if((i <= X) && (j >= Y)) a.at((X - i) + (j - Y) + 1)++;
      else if((i > X) && (j < Y)) {
        if((j - i) <= ((i - X) + (Y - j) + 1)) a.at(j - i)++;
        else a.at((i - X) + (Y - j) + 1)++;
      }
      else if((i <= X) && (j <= Y)) {
        if((j - i) <= ((X - i) + (Y - j) + 1)) a.at(j - i)++;
        else a.at((X - i) + (Y - j) + 1)++;
      }
      else if((i >= X) && (j >= Y)) {
        if((j - i) <= ((i - X) + (j - Y) + 1)) a.at(j - i)++;
        else a.at((i - X) + (j - Y) + 1)++;
      }
    }
  }
  for(ll i = 1; i < N; i++) cout << a.at(i) << endl;
}


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

int main()
{
    
long long int h,w;
cin>>h>>w;
int c;int x;
long long int c1,c2;
x=h/2;
if(h==1 || w==1)
{
cout<<"1";
exit(0);
}
if(h%2!=0 && w%2!=0)
{
    c1=w/2+1;
    c2=c1-1;
    cout<<(c1*((h/2)+1)+c2*(h/2));
}
else
if(h%2==0 and w%2!=0)
{
    c1=w/2+1;
    c2=c1-1;
    cout<<(c1*x+c2*x);
}
else
if(w%2==0)
{
    
    cout<<((w/2)*h);
}
}


Measured memory_bytes: 256
ai = []
while True:
    q = list(map(int,input().split()))
    if sum(q) == 0:
        break
    ai.append(q)
    
for i in range(len(ai)):
    if ai[i][0] > ai[i][1]:
        print(ai[i][1],ai[i][0])
    else:
        print(ai[i][0],ai[i][1])


Measured memory_bytes: 6128
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
vector<int> vec;
queue<int> test;

long long f(int i)
{
	if (i == 0)
		return vec[i] - 1;
	return f(i - 1) + (vec[i] - 1);
}

int main()
{
	int n;
	scanf("%d", &n);
	vec.resize(n);
	for (int i = 0; i < n; i++)
		scanf("%d", &vec[i]);
	cout << f(vec.size() - 1);
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<vector<char>>date(2,vector<char>(3));
  for(int i=0;i<2;i++){
  for(int j=0;j<3;j++){
  cin>>date.at(i).at(j);
  }
  }
if(date.at(0).at(0)==date.at(1).at(2)&&date.at(0).at(1)==date.at(1).at(1)&&date.at(0).at(2)==date.at(1).at(0)){
cout<<"YES"<<endl;

}
  else{
  cout<<"NO"<<endl;
  
  }
}

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

int main()
{
    int n;
    scanf("%d", &n);
    int a = 0, b = 0, ans = 0;
    char s[10000][10] = {0};
    int l[10000] = {0};
    int i, j, k, sa = 0;

    for (i = 0; i < n; i++)
    {
        scanf("%s", s[i]);
        j = 0;
        while (s[i][j])
        {
            l[i]++;
            j++;
        }
    }

    for (i = 0; i < n; i++)
    {
        k = 0;
        if (s[i][0] == 'B')
        {
            b++;
            k++;
        }
        if (s[i][l[i] - 1] == 'A')
        {
            a++;
            k++;
        }
        if (k == 2)
        {
            sa++;
        }
        for (j = 0; j < l[i] - 1; j++)
        {
            if (s[i][j] == 'A' && s[i][j + 1] == 'B')
            {
                ans++;
            }
        }
    }
    a -= sa;
    b -= sa;
    if (sa == 0)
    {
        if (a > b)
        {
            ans += b;
        }
        else
        {
            ans += a;
        }
    }
    else
    {
        if (a + b > 0)
        {
            if (a > b)
            {
                ans += sa + b;
            }
            else
            {
                ans += sa + a;
            }
        }
        else
        {
            ans += sa - 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    int sum=0;
    for(int i=0;i<s.size();i++){
		sum+=s[i]-'0';
	}
	if(stoi(s)%sum==0){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
template <typename T> using lim = numeric_limits<T>;
const int M = 1'000'000'007;
int n, x, y, z;
const int N = 40, XYZ = 17;
ll mem[N + 1][1 << XYZ][2];
ll C(int n, int d, bool has_xyz) {
    ll& ans = mem[n][d][has_xyz];
    if(ans == -1) {
        if(n == 0) {
            ans = has_xyz;
        } else {
            ans = 0;
            for(int i = 1; i <= 10; i++) {
                int nd = ((d << i) | (1 << (i - 1))) & ((1 << (x + y + z)) - 1);
                bool can = nd & (1 << (x - 1)) and nd & (1 << (x + y - 1)) and nd & (1 << (x + y + z - 1));
                ans = (ans + C(n - 1, nd, has_xyz or can)) % M;
            }
        }
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> x >> y >> z;
    memset(mem, -1, sizeof mem);
    cout << C(n, 0, 0) << endl;
    return 0;
}


Measured memory_bytes: 84224
import itertools
import math

N = int(input())
X = []
Y = []

for i in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)

def des(i, j):
    return math.sqrt( (X[i] - X[j])**2.0 + (Y[i] - Y[j])**2.0 )

s = 0
for c in itertools.combinations(range(N), 2):
    s += des(c[0], c[1])

print(s*2 / N)


Measured memory_bytes: 3064
//abc153_b.cpp
//Sat Feb 22 18:08:32 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

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

	int total = 0;
	for (int i=0;i<n;i++){
		int temp;
		cin >> temp;
		total+=temp;
	}

	if (total>=h){
		cout << "Yes" << endl;
	}else {
		cout << "No" << endl;
	}

}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		Main mainObj = new Main();
		mainObj.solve();
	}

	public void solve() throws IOException {
		FastScanner fs = new FastScanner();
		int a = fs.nextInt();
		int b = fs.nextInt();
		
		System.out.println(a*b);
	}

	

	public class FastScanner {

		BufferedReader reader;
		private StringTokenizer st;

		public FastScanner() {
			st = null;
			reader = new BufferedReader(new InputStreamReader(System.in));
		}

		public String next() throws IOException {
			if (st == null || !st.hasMoreElements()) {
				st = new StringTokenizer(reader.readLine());
			}
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			st = null;
			String readLine = null;
			readLine = reader.readLine();
			return readLine;
		}

		public int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		public int[] nextIntArr(int n) throws NumberFormatException, IOException {
			int[] retArr = new int[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextInt();
			}
			return retArr;
		}

		public long[] nextLongArr(int n) throws NumberFormatException, IOException {
			long[] retArr = new long[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextLong();
			}
			return retArr;
		}

		public void close() throws IOException {
			reader.close();
		}
	}


}


Measured memory_bytes: 32556
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#include <deque>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

int main() {
  string s; cin >> s;
  int n = s.size();
  vector<int> ans(n);
  rep(ri, 2) {
    int cnt= 0;
    rep(i, n) {
      if(s[i] == 'R') cnt++;
      else {
        ans[i] += cnt/2;
        ans[i-1] += (cnt+1)/2;
        cnt = 0;
      }
    }
    reverse(ans.begin(), ans.end());
    reverse(s.begin(), s.end());
    rep(i, n) {
      if(s[i] == 'L') s[i] = 'R';
      else s[i] = 'L';
    }
  }
  rep(i, n) {
    if(i) cout << " ";
    cout << ans[i];
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, s, n) for(int i = s; i < (int)n; i++)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= (int)n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MP make_pair
#define EACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define NCLR(a) memset((a), -1 ,sizeof(a))
#define dump(x) cout << #x << " = " << (x) << "\n";
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << "\n";
#define sq(n) (n) * (n)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef priority_queue<int> maxpq;
typedef priority_queue< int, vector<int>, greater<int> > minpq;
static const double EPS = 1e-10;
static const double PI = acos( -1.0 );
static const int mod = 1000000007;
static const int INF = 1 << 30;
static const LL LL_INF = 1152921504606846976;
static const int dx[] = { -1, 0, 1, 0, 1, -1, 1, -1 };
static const int dy[] = { 0, -1, 0, 1, 1, 1, -1, -1 };



int ans;
string str;
set<string> can_str;

int main() {
	while ( cin >> str && str != "0" ) {
		int ans = -1;
		queue<pair<string, int> > q;
		q.push( make_pair( str, 0 ) );
		while ( q.size() ) {
			string s = q.front().first;
			int n = q.front().second;
			q.pop();
			if ( can_str.count( s ) ) {
				continue;
			}
			can_str.insert( s );
			bool can_break = true;
			for ( int i = 1; i < s.size(); i++ ) {
				if ( s[ i ] != s[ i - 1 ] ) {
					can_break = false;
					break;
				}
			}
			if ( can_break ) {
				ans = n;
				break;
			}
			for ( int i = 1; i < s.size(); i++ ) {
				if ( s[ i ] != s[ i - 1 ] ) {
					string s_copy = s;
					if ( s[ i ] == 'r' ) {
						if ( s[ i - 1 ] == 'g' ) {
							s[ i ] = s[ i - 1 ] = 'b';
						}
						else {
							s[ i ] = s[ i - 1 ] = 'g';
						}
					}
					else if ( s[ i ] == 'g' ) {
						if ( s[ i - 1 ] == 'r' ) {
							s[ i ] = s[ i - 1 ] = 'b';
						}
						else {
							s[ i ] = s[ i - 1 ] = 'r';
						}
					}
					else if ( s[ i ] == 'b' ) {
						if ( s[ i - 1 ] == 'g' ) {
							s[ i ] = s[ i - 1 ] = 'r';
						}
						else {
							s[ i ] = s[ i - 1 ] = 'g';
						}
					}
					q.push( make_pair( s, n + 1 ) );
					s = s_copy;
				}
			}
		}
		if ( ans < 0 ) {
			printf( "NA\n" );
		}
		else {
			printf( "%d\n", ans );
		}
		can_str.clear();
	}
	return 0;
}

Measured memory_bytes: 2964
import sys
input = sys.stdin.readline
h, w = map(int,input().split())
A = [list(map(int,input().split())) for i in range(h)]
B = [list(map(int,input().split())) for i in range(h)]
 
C = [[0] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])
 
M = [[0] * w for i in range(h)]
 
s = 0
Q = []
for i in range(h):
    Q.append([i, 0])
for i in range(1, w):
    Q.append([0, i])
for i in range(1, h):
    for j in range(1, w):
        Q.append([i, j])

m = 80
M[0][0] = (1 << m + C[0][0]) | (1 << m - C[0][0])

for s in range(len(Q)):
    i = Q[s][0]
    j = Q[s][1]
    if i+1 < h:
        M[i+1][j] |= (M[i][j] << m + C[i+1][j]) | (M[i][j] << m - C[i+1][j])
    if j+1 < w:
        M[i][j+1] |= (M[i][j] << m + C[i][j+1]) | (M[i][j] << m - C[i][j+1])

        # N[i][j+1] = max(N[i][j+1], N[i][j] + C[i][j+1])
 
# print(M[-1][-1])
b = bin(M[-1][-1])
ans = float("inf")
for i in range(len(b)):
    if b[-1-i] == "1":
        ans = min(ans, abs(i - m*(h+w-1)))
print(ans)

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

struct E {
    int t;
    char type;
    E(int t, char type) : t(t), type(type) {}
    bool operator<(const E& o) const {
        return (t == o.t ? type < o.type : t < o.t);
    }
};

int main() {
    int n;
    while (scanf("%d", &n), n != 0) {
        vector<E> es;
        for (int i = 0; i < n; i++) {
            int h, m, s;
            int _h, _m, _s;
            scanf("%d:%d:%d %d:%d:%d", &h, &m, &s, &_h, &_m, &_s);
            es.push_back(E(h*3600+m*60+s, 'o'));
            es.push_back(E(_h*3600+_m*60+_s, 'i'));
        }
        sort(es.begin(), es.end());
        int cnt = 0;
        int total = 0;
        for (int i = 0; i < es.size(); i++) {
            //cout << es[i].t << ':' << es[i].type << ' ';
            if (es[i].type == 'o') {
                cnt++;
                total = max(total, cnt);
            } else {
                cnt--;
            }
        }
        cout << total << endl;
    }
    return 0;
}

Measured memory_bytes: 1460
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	ll N,X;
	cin>>N>>X;
	vector<lp> table (N+1);
	table[0].first = 1;
	table[0].second = 1;
	REP(i,N){
		table[i].first = table[i-1].first*2 + 3LL;
		table[i].second = table[i-1].second*2 + 1LL;
	}
	ll ans = -1LL;
	++X;
	while(X>0){
		++ans;
		--X;
		for(int i = N; i>=0; --i){
			if(table[i].first <= X){
				ans += table[i].second;
				X -= table[i].first;
				N = i;
				break;
			}
			--X;
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0LL,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,n) RFOR(i,0LL,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define COUNT(a,x,y) upper_bound(all(a), y) - lower_bound(all(a), x)
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())
#define SUM(a) accumulate(all(a),0LL)
#define scan(x) scanf("%lld",&x)
#define print(x) printf("%lld\n",x)
#define print2(x) printf("%lld ",x)
#define pb push_back
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
const ll inf = 2222222222222222222LL;
const ll mod = 1000000007LL;

ll n = 0, m = 0, ans = 0, cnt = 0, tmp = 0, ma = -inf, mi = inf;
string s;
bool ok = true, flag = false;
ll dx[5] = { 1,-1,0,0,0 }, dy[5] = { 0,0,1,-1,0 };
ll ddx[9] = { 1,-1,0,0,1,1,-1,-1,0 }, ddy[9] = { 0,0,1,-1,1,-1,1,-1,0 };
#pragma endregion
#define MAX 333333

vll pr;
bool is[MAX + 1];

void AllPrime(ll x) {
  rep(i, x + 1) is[i] = true;
  is[0] = false;
  is[1] = false;
  rep(i, x + 1) {
	if (is[i]) {
	  pr.pb(i);
	  for (ll j = 2 * i;j <= x;j += i) is[j] = false;
	}
  }
}

vll fac, inv, invfac;
void comb_set(ll x = MAX) {
  fac.resize(x + 1, 0);
  invfac.resize(x + 1, 0);
  inv.resize(x + 1, 0);
  fac[0] = inv[1] = invfac[0] = 1;
  FOR(i, 1, x + 1) (fac[i] = fac[i - 1] * i) %= mod;
  FOR(i, 2, x + 1) (inv[i] = (mod - mod / i) * inv[mod%i]) %= mod;
  FOR(i, 1, x + 1) (invfac[i] = invfac[i - 1] * inv[i]) %= mod;
}
ll comb(ll x, ll y) {
  if (x < y) return 0;
  return fac[x] * invfac[x - y] % mod * invfac[y] % mod;
}

int main(void) {
  cin >> n >> m;
  AllPrime(MAX);
  comb_set();

  ans = 1;
  rep(i, pr.size()) {
	cnt = 0;
	while (m%pr[i] == 0) {
	  m /= pr[i];
	  cnt++;
	}
	if (cnt) (ans *= comb(n + cnt - 1, cnt)) %= mod;
  }
  
  if (m != 1) (ans *= n) %= mod;
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 8700
//  cout << char(i+48) << endl;//なぜかaは47と得る時がある。+48で出力もaにできる。
//  cout << char(97) << endl;//アスキーコードでaを出力
// sort(b.begin(), b.end());//bという配列を小さい方からソート
// reverse(b.begin(), b.end());//bという配列をリターン
// 10桁でdouble出力するパターン１ 
// printf("%.10f\n", ma);
// 10桁でdouble出力するパターン２
//cout << fixed << setprecision(10);
//  cout << ma << endl;

/*01 02 03 12 13 23　と６回見ていくパターン 
for(int i=0;i<n-1;i++){
  for(int j=i+1;j<n;j++){
    }
  }
*///vector<vector<int>> data(3, vector<int>(4));//int型の2次元配列(3×4要素の)の宣言
//int64_t a;
//10のi乗pow(10, i);
/*string s; stringでの文字列を数字型に変える方法
  cin >> s;
  rep(i,s.size()-2) {
  int a= (s.at(i)-'0')*100 + (s.at(i+1)-'0')*10+ s.at(i+2) -'0';
    */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int keisan(ll n){
  ll cnt = 0;
  while(n>0){
    n/=10;
    cnt++;
  }
  return cnt;
}

int main() {
  ll n;
  cin >> n;
  ll ma=1000000;
  ll mi =10000000000;
  for(int i=1;i<=pow(n,0.5);i++){
    if(n%i ==0){
    ll k=n/i;
    int a = keisan(i);
    int b = keisan(k);
    ma = max(a,b);
    mi = min(mi,ma);
    }//for end
  }
  cout << mi << endl;
//  cout << pow(i,0.5) << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define LL long long
#define FOR(i,c) for(__typeof(c.begin()) i = c.begin(); i != c.end(); i++)
#define F first
#define S second
using namespace std;

const LL mod = 1e9 + 7;

template<typename T> T gcd(T a, T b) { return b == 0?a: gcd(b, a % b); }
template<typename T> T LCM(T a, T b) { return a*(b/gcd(a, b)); }
template<typename T> T expo(T base, T e, T mod) { T res = 1;
  while(e > 0) { if(e&1) res = res * base % mod; base = base * base % mod; e >>= 1; }
  return res;
}
template<typename T, typename S> T expo(T b, S e){if(e <= 1)return e == 0?1: b;\
	return (e&1) == 0?expo((b*b), e>>1): (b*expo((b*b), e>>1));}
template<typename T, typename S> T modinv(T a, S mod) { return expo(a, mod-2, mod); }
template<class T, class S> std::ostream& operator<<(std::ostream &os, const std::pair<T, S> &t) {
	os<<"("<<t.first<<", "<<t.second<<")";
	return os;
}
template<class T> std::ostream& operator<<(std::ostream &os, const std::vector<T> &t) {
	os<<"["; FOR(it,t) { if(it != t.begin()) os<<", "; os<<*it; } os<<"]";
	return os;
}

const int MAXN = 1e3;
LL grid[MAXN][MAXN];
bool covered[MAXN][MAXN];

int main() {
  ios_base::sync_with_stdio(false);
	LL H, W, h, w;
	cin >> H >> W >> h >> w;
	for(int i = 1; i <= H; i++) {
		for(int j = 1; j <= W; j++) {
			grid[i][j] = 1;
		}
	}
	for(int r = 1; r <= H - h + 1; r++) {
		for(int c = 1; c <= W - w + 1; c++) {
			if(!covered[r][c]) {
				grid[r + h - 1][c + w - 1] = -h*w;
				for(int a = 0; a < h; a++) {
					for(int b = 0; b < w; b++) {
						covered[r + a][c + b] = true;
					}
				}
			}
		}
	}
	LL x = 0;
	for(int i = 1; i <= H; i++) {
		for(int j = 1; j <= W; j++) {
			if(grid[i][j] < 0) {
				x++;
			}
		}
	}
	LL alpha = H*W - x;
	if(H*W == x*h*w) {
		cout << "No\n";
	} else {
		cout << "Yes\n";
		LL den = max(1ll, H*W - x*h*w);
		LL a = x/den;
		a++;
		for(int i = 1; i <= H; i++) {
			for(int j = 1; j <= W; j++) {
				if(grid[i][j] > 0) {
					grid[i][j] = a;
				} else if(grid[i][j] < 0) {
					grid[i][j] = - (a * (h*w - 1) + 1);
				}
				cout << grid[i][j] << ' ';
			}
			cout << '\n';
		}
		/*
		for(int i = 1; i <= H - h + 1; i++) {
			for(int j = 1; j <= W - w + 1; j++) {
				LL sum = 0;
				for(int a = 0; a < h; a++) {
					for(int b = 0; b < w; b++) {
						sum += grid[i + a][j + b];
					}
				}
				assert(sum < 0);
			}
		}
		*/
	}
  return 0;
}


Measured memory_bytes: 7040
#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

int n, a, b, c, d;

void read_input()
{
    cin >> n >> a >> b >> c >> d;
}

void solve()
{
    int k = abs(a - b);
    for(int i = 0; i < n - 1; ++i)
        if(c * 1LL * (n - 1 - i) - d * 1LL * i <= k && k <= d * 1LL * (n - 1 - i) - c * 1LL * i)
        {
            cout << "YES\n";
            return;
        }
    cout << "NO\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    solve();
}



Measured memory_bytes: 3672
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = (l); i < (r); i++)
#define ALL(x) (x).begin(), (x).end()     //昇順
#define RALL(x) (x).rbegin(), (x).rend()  // 降順
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"
const long long mod = 1e9 + 7;
typedef long long ll;
typedef priority_queue<int> PQ;
typedef vector<long long> VL; // VL a(n);
typedef vector<bool> VB;
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<char> VC;
typedef vector<VS> VSS;
typedef vector<VC> VCC;
typedef vector<VL> VLL; // VII a(n,VI(m)) n * m
typedef pair<ll, ll> PL;
typedef map<ll, ll> MP; // MP a;
typedef vector<pair<ll, ll>> PS;

template <class T, class U>
bool chmax(T &a, U b) {
  if (a <= b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T, class U>
bool chmin(T &a, U b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &v) {
  os << "{";
  rep(i, (int)v.size()) { os << v[i] << (i < v.size() - 1 ? ", " : ""); }
  os << "}";
  return os;
}

// g++ -std=c++11 prac.cpp
// operator << (cout,a);
// chmin(min,a)

int main() {
  ll n,k,m,x=0,y=0,z = 0,h=0,w=0,ans=0,sum = 0, Max = -1, Min = 3e9+1;
  string s,t;
  bool ok=true; 
  cin >> n;
  MP mp;
  rep(i,n){
    cin >> x;
    auto itr = mp.find(x);
    if(itr != mp.end()){
        itr->second++;
    }
    else{
      mp.insert(make_pair(x,1));
    }
  }
  for( auto i = mp.begin(); i != mp.end();i++ ) { 
    if(i->first != i->second){
      if(i->first < i->second){
        ans += i->second - i->first;
      }
      else{
        ans += i->second;
      }
    }
  }

  pri(ans);
  return 0;
}

Measured memory_bytes: 9412
import Control.Monad
main = do
  [n,m] <- map read . words <$> getLine
  lr <- replicateM m $ do
    [a,b] <- map read . words <$> getLine
    return (a,b)
  let (l,r) = unzip lr
  print $ max 0 (minimum r - maximum l + 1)

Measured memory_bytes: 66940
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	
	int[] p=new int[200000];
	{
		Arrays.fill(p, -1);
	}
	
	int root(int x) {
		return p[x]==-1?x:(p[x]=root(p[x]));
	}
	
	void unite(int x,int y) {
		x=root(x);y=root(y);
		if (x!=y) p[x]=y;
	}
	
	boolean equiv(int x,int y) {
		return root(x)==root(y);
	}
	
	void run() {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int Q=sc.nextInt();
		PrintWriter pw=new PrintWriter(System.out);
		while (Q-->0) {
			int t=sc.nextInt();
			int u=sc.nextInt();
			int v=sc.nextInt();
			if (t==0) unite(u,v);
			else pw.println(equiv(u,v)?1:0);
		}
		pw.flush();
	}
	
	void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));}
}


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

int main(){
    int n;cin>>n;
    string ss;cin>>ss;
    int l=0,r=0;
    int tot=0;
    rep(i,n){
        if(ss[i]=='(')tot++;
        else{
            if(tot==0)l++;
            else tot--;
        }
    }
    tot=0;
    for(int i=n-1;i>=0;--i){
        if(ss[i]==')')tot++;
        else{
            if(tot==0)r++;
            else tot--;
        }
    }

    rep(i,l)cout<<'(';
    cout<<ss;
    rep(i,r)cout<<')';
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		sc.close();

		String ans = "No";
		if ( A == B && A != C ) {
			ans = "Yes";
		} else if ( A == C && A != B ) {
			ans = "Yes";
		} else if ( B == C && A != B ) {
			ans = "Yes";
		}
		System.out.println(ans);
	}
}


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

int main()
{
    ll N, D;
    cin >> N >> D;
    ll ans(0);
    for (ll i = 0; i < N; ++i)
    {
        ll X, Y;
        cin >> X >> Y;
        if (X * X + Y * Y <= D * D)
        {
            ++ans;
        }
    }
    cout << ans << endl;
}


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

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
#define ALL(x) x.begin(),x.end()
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int N;
const ll INF = 1e18;

int main()
{
	scanf("%d",&N);
	vector<ll> A(N);
	FOR(i,0,N){
		scanf("%lld",&A [i]);
	}

	ll ans = INF,sum = 0,cnt = 0;
	FOR(i,0,N){
		sum += A [i];
		if(i % 2 == 0){
			ll t = max(0ll,1 - sum);
			sum += t;
			cnt += t;
		}
		else{
			ll t = max(0ll,sum + 1);
			sum -= t;
			cnt += t;
		}
	}
	chmin(ans,cnt);
	sum = 0;
	cnt = 0;
	FOR(i,0,N){
		sum += A [i];
		if(i % 2 == 0){
			ll t = max(0ll,sum + 1);
			sum -= t;
			cnt += t;
		}
		else{
			ll t = max(0ll,1 - sum);
			sum += t;
			cnt += t;
		}
	}
	chmin(ans,cnt);

	printf("%lld\n",ans);

	return 0;
}


Measured memory_bytes: 1024
n = int(input())

dp = [float('inf')] * (n + 1)
dp[0] = 0
nums = [1]
i = 1
while 6 ** i <= n:
    nums.append(6 ** i)
    i += 1
i = 1
while 9 ** i <= n:
    nums.append(9 ** i)
    i += 1
nums.sort()
for i in range(n + 1):
    for j in range(len(nums)):
        num = nums[j]
        if i - num >= 0:
            dp[i] = min(dp[i], dp[i - num] + 1)
ans = dp[n]
print(ans)


Measured memory_bytes: 74488
n = int(input())
dic = {}
for _ in range(n):
    s = input()
    try:
        dic[s] += 1
    except:
        dic[s] = 1

num_max = 0
words = []
for k in dic.keys():
    num = dic[k]
    if num_max == num:
        words.append(k)
    elif num_max < num:
        words = [k]
        num_max = num
    

words = sorted(words)
for w in words:
    print(w)

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

using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VD = vector<double>;
using VVD = vector<VD>;
using VS = vector<string>;
using PII = pair<int, int>;
using VPII = vector<PII>;
using VL = vector<long long>;
using VVL = vector<VL>;

#define sz(var) (int)var.size()
#define REP(var, start, end) for(int var = start; var < (int)end; ++var)
#define CLEAR(var, with) memset(var, with, sizeof(var))
#define ALL(x) x.begin(), x.end()
#define LL long long
#define ULL unsigned long long
#define TIME cout << "Time elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms" << endl;

VS A, B;
int n, m;
bool isInside(int y, int x)
{
	if(y + m - 1 > n - 1 || x + m - 1 > n - 1)
		return false;

	for(int i = y, r = 0; r < m && i < y + m; ++i, ++r)
		for(int j = x, c = 0; c < m && j < x + m; ++j, ++c)
			if(A[i][j] != B[r][c])
				return false;
	return true;
}

bool isIncluded()
{
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < n; ++j)
			if(isInside(i, j))
				return true;
	return false;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
#ifndef ONLINE_JUDGE
//	freopen("tmp.in", "r", stdin);
//	freopen("tmp.out", "w", stderr);
#endif
	cin >> n >> m;

	A = VS(n); B = VS(m);
	REP(i, 0, n) cin >> A[i];
	REP(i, 0, m) cin >> B[i];

	cout << (isIncluded() ? "Yes" : "No") << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include <string>
#include<math.h>
#include<stdio.h>
#include<vector>
#define rep(i,n)for(int i=0;i<n;i++)
//printf("%.yf\n",x); xを小数点以下y桁で
using namespace std;
int main() {
	int a, b;
	cin >> a >> b;
	if (a == b) {
		cout << a + b << endl;
	}
	else {
		int c = max(a, b);
		cout << c + c - 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
// #define int long long
#define mod (int)(1e9 + 7)
#define pb push_back
#define ll long long int
using namespace std;
typedef pair<long long int,long long int> pii;

int main(){

  int n,m;
  cin>>n>>m;

  long long int l,r,c;
  vector<vector<pii> > v(n+1,vector<pii>());
  for(int i=2;i<=n;i++){
    v[i].pb(pii(i-1,0));
  }
  
  for(int i=1;i<=m;i++){
    cin>>l>>r>>c;
    v[l].pb(pii(r,c));
  }

  vector<long long int> d(n+1,-1);
  
  priority_queue<pii,vector<pii>, greater<pii> > q;
  d[1]=0;
  for(int i=0;i<v[1].size();i++){
    q.push(pii(v[1][i].second, v[1][i].first));
  }
  int i=0;
  while(!q.empty()){
    pii t = q.top();q.pop();
    long long int ima=t.second;
    long long int cost=t.first;
    if(d[ima]!=-1 && cost>=d[ima]) continue;
    //printf("%d : %d %d\n",i++, ima, cost);
    d[ima]=cost;
    
    for(int i=0;i<v[ima].size();i++){
      long long int next=v[ima][i].first;
      long long int next_c=d[ima] + v[ima][i].second;
      if(d[next]==-1 || next_c < d[next]){
        q.push(pii(next_c,next));
      }
    }
  }
  cout<<d[n]<<endl;
    
  return 0;
}


Measured memory_bytes: 10744
#include <iostream>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>
 
using namespace std;
typedef long long int ll;

#define MOD 1000000007LL

ll N;
ll A, B, C;
vector<int> s;
vector<char> aq;

bool exec(int, int, int, int);

int main()
{
  int i;
  string si;

  cin >> N >> A >> B >> C;
  s.resize(N);
  for (i=0; i<N; i++) {
    cin >> si;
    if (si == "AB") {s[i] = 1; continue;}
    if (si == "AC") {s[i] = 2; continue;}
    if (si == "BC") {s[i] = 3; continue;}
  }

  aq.resize(N);
  if (!exec(0, A, B, C))
    printf("No\n");

  return 0;
}

bool exec(int i, int a, int b, int c) {
  bool r = false;
  if (i == N) {
//printf("%d (%d, %d, %d)\n", i, a, b, c);
    printf("Yes\n");
    for (int j=0; j<N; j++) {
      printf("%c\n", aq[j]);
    }
    return true;
  }
//printf("%d [%d] (%d, %d, %d)\n", i, s[i], a, b, c);
  switch(s[i]) {
  case 1:
    if (b>0) {
      aq[i] = 'A';
      r = exec(i+1, a+1, b-1, c);
      if (!r) {
        if (a>0) {
          aq[i] = 'B';
          r = exec(i+1, a-1, b+1, c);
        }
      }
    } else if (a>0) {
      aq[i] = 'B';
      r = exec(i+1, a-1, b+1, c);
    }
    break;
  case 2:
    if (c>0) {
      aq[i] = 'A';
      r = exec(i+1, a+1, b, c-1);
      if (!r) {
        if (a>0) {
          aq[i] = 'C';
          r = exec(i+1, a-1, b, c+1);
        }
      }
    } else if (a>0) {
      aq[i] = 'C';
      r = exec(i+1, a-1, b, c+1);
    }
    break;
  case 3:
    if (b>0) {
      aq[i] = 'C';
      r = exec(i+1, a, b-1, c+1);
      if (!r) {
        if (c>0) {
          aq[i] = 'B';
          r = exec(i+1, a, b+1, c-1);
        }
      }
    } else if (c>0) {
      aq[i] = 'B';
      r = exec(i+1, a, b+1, c-1);
    }
    break;
  }
  return r;
}



Measured memory_bytes: 11656
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
const long double PI = (acos(-1));
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int ctoi(char c)
{
    switch (c)
    {
    case '0':
        return 0;
    case '1':
        return 1;
    case '2':
        return 2;
    case '3':
        return 3;
    case '4':
        return 4;
    case '5':
        return 5;
    case '6':
        return 6;
    case '7':
        return 7;
    case '8':
        return 8;
    case '9':
        return 9;
    default:
        return 0;
    }
}
int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    for (int i = 1; i <= b; i++)
    {
        if ((i * a) % b == c)
        {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
    return 0;
}

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

 #define rep(i, a, b) for (int i = a; i <= b; i++)

 int n, x, ans;

int main()
{
	scanf("%d", &n);
	ans = 0;
	rep(i, 1, n) {
		scanf("%d", &x);
		if (x & 1) ans ^= 1;
	}
	puts(ans ? "NO" : "YES");
	return 0;
}


Measured memory_bytes: 128
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

def input():
    return stdin.readline()[:-1]

def main():
    from builtins import int, map
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    ng = {n: 0 for n in range(1, N + 1)}
    for _ in range(M):
        ai, bi = map(int, input().split())
        ng[ai] = max(ng[ai], H[bi - 1])
        ng[bi] = max(ng[bi], H[ai - 1])

    count = 0
    for v in range(1, N + 1):
        if H[v - 1] > ng[v]:
            count += 1
    print(count)

if __name__ == '__main__':
    main()

Measured memory_bytes: 93716
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<V>;
using VVV = vector<VV>;
using VL = vector<ll>;
using VVL = vector<VL>;
using VVVL = vector<VVL>;
template<class T> using VE = vector<T>;
template<class T> using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
ll upper = MOD + MOD;
ll under = -upper;
ll UPPER = MOD * MOD;
ll UNDER = -UPPER;
const long double pi = 3.141592653589793;
int main() {
	string s, t;
	cin >> s >> t;
	int ans = upper;
	int n = s.size(), m = t.size();
	rep(i, n - m + 1) {
		int tmp = 0;
		rep(j, m) {
			if (s[i + j] != t[j]) tmp++;
		}
		chmin(ans,tmp);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3596
module Main where

import           Control.Applicative
import           Data.List

main :: IO ()
main = do
    [m, n] <- map read . words <$> getLine
    putStrLn $ solve2 m n

solve2 :: Int -> Int -> String
solve2 m n | m <= n = concat $ replicate n (show m)
           | m > n  = concat $ replicate m (show n)



Measured memory_bytes: 508
#include <cstdio>
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
#include <cmath>
#include <iomanip>
#include <regex>
#include <bits/stdc++.h>
#include <string>
using namespace std;

long long GCD(long long x, long long y) {
    return y ? GCD(y, x%y) : x;
}

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}


int main(){
    long long A,B;
    cin>>A>>B;
    long long gcd = GCD(A,B);
    vector<pair<long long, long long> > v;
    v = prime_factorize(gcd);
    cout<<1+v.size()<<endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    
    int n,m,c;
    cin>>n>>m>>c;
    int B[m];
    int A[n][m];
    
    for(int i=0;i<m;i++){
        cin>>B[i];
    }
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>A[i][j];
        }
    }
    
    int ct=0, ans;
    for(int i=0;i<n;i++){
        ans=c;
        for(int j=0;j<m;j++){
              ans+=A[i][j]*B[j];
        }
        if(ans>0) ct++;
    }
    cout<<ct<<endl;
}


Measured memory_bytes: 256
s = input()
a = 0
z = 200001
for i in range(len(s)):
    if s[i] == 'A':
        a = i
        break
for i in range(len(s)-1, 0, -1):
    if s[i] == 'Z':
        z = i
        break
print(z-a+1)

Measured memory_bytes: 3516
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <string>
#include <math.h>
#include <cstdlib>
#include <istream>
#include <sstream>
#include <cctype>
#define fore(i,x,y) for(long long i=x;i<y;i++)
typedef long long ll;
using namespace std;
int main()
{
	char a;
	cin >> a;
	if(a=='a'||a=='i'||a=='u'||a=='e'||a=='o'){
		cout << "vowel" << endl;
	}
	else{
		cout << "consonant" << endl;
	}
}

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

bool compare(pair<string, int> a, pair<string, int> b) {
	// 基本はfirstで比較
    if(a.first != b.first){
        return a.first < b.first; // 昇順
    }

    return a.second > b.second; // 降順
}


int main() {
	int N = 0;
	cin >> N;
	vector<book> books(N);
	vector<int> indexes(N);

	repeat(i, N) {
		string city = "";
		int points = 0;
		cin >> city >> points;
		books[i].first = city;
		books[i].second = points;
		indexes[i] = points;
	}

  // sort(books.begin(), books.end());
  sort(books.begin(), books.end(), compare);
	repeat(i, N) {
		int point = books[i].second;
		auto itr = find(indexes.begin(), indexes.end(), point);
		int index = distance(indexes.begin(), itr);
		cout << index + 1 << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){

int X ;   //変数を宣言

cin>>X;	//外部入力を変数を1つ読み込む

cout<<X*X*X<<endl;	//面積・空白スペース・州の長さ・改行を出力
//ここに処理を記述していきます（この行は残しておいても、消しても大丈夫です）


return 0;
}


Measured memory_bytes: 3108