akhauriyash/Code-Regression huggingface dataset:
n=int(input())
s=input()
a=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
b=[["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"],
   ["B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A"],
   ["C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B"],
   ["D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C"],
   ["E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D"],
   ["F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D","E"],
   ["G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D","E","F"],
   ["H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D","E","F","G"],
   ["I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D","E","F","G","H"],
   ["J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D","E","F","G","H","I"],
   ["K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D","E","F","G","H","I","J"],
   ["L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D","E","F","G","H","I","J","K"],
   ["M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D","E","F","G","H","I","J","K","L"],
   ["N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D","E","F","G","H","I","J","K","L","M"],
   ["O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D","E","F","G","H","I","J","K","L","M","N"],
   ["P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O"],
   ["Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P"],
   ["R","S","T","U","V","W","X","Y","Z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q"],
   ["S","T","U","V","W","X","Y","Z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R"],
   ["T","U","V","W","X","Y","Z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S"],
   ["U","V","W","X","Y","Z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T"],
   ["V","W","X","Y","Z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U"],
   ["W","X","Y","Z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V"],
   ["X","Y","Z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W"],
   ["Y","Z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X"],
   ["Z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y"],
  ]
c=[]
for i in  range(len(s)):
    cnt=a.index(s[i])
    c.append(str(b[cnt][n%26]))
for i in range(len(s)):
    print(c[i],end="")

Measured memory_bytes: 4980
#pragma region include
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <cstdio>
#include <tuple>
#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i,n,m) for(int i = (int)(n); i < int(m); i++)
#define MOD (1e9+7)
#define INF (1e9)
#define LLINF (4e18)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
void input() {}
template<typename... R> void input(int& f, R&... r) { scanf("%d", &f); input(r...); }
template<typename... R> void input(double& f, R&... r) { scanf("%lf", &f); input(r...); }
template<typename... R> void input(ll& f, R&... r) { scanf("%lld", &f); input(r...); }
template<typename... R> void input(char& f, R&... r) { scanf("%c", &f); input(r...); }
template<typename... R> void input(string& f, R&... r) { cin >> f; input(r...); }
template<typename T, typename... R> void input(vector<T>& f, R&... r) { REP(i, f.size())input(f[i]); input(r...); }
#pragma endregion

int main() {
    int N; input(N);
    map<int, int> mp;
    REP(i, N) {
        int a; input(a);
        mp[a]++;
    }
    int ans = 0;
    for (auto m : mp) {
        if (m.first > m.second) {
            ans += m.second;
        }
        else {
            ans += m.second - m.first;
        }
    }
    cout << ans << endl;
    getchar(); getchar();
}

Measured memory_bytes: 4736
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define Clear(a) a = decltype(a)()
#define all(a) a.begin(),a.end()
#define vec vector
typedef long long ll;
typedef pair<int,int> p;
//const ll big=998244353;
const ll big=1000000007;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
ll max(ll x,ll y){
if(x>y)return x;
else return y;
}
ll min(ll x,ll y){
if(x<y)return x;
else return y;
}
ll expm(ll x,ll y){
    if(y==0)return 1;//0^0=1
    if(x==1||x==0)return x;
    if(y%2==1)return (expm(x,y-1)*x)%big;
    ll t=expm(x,y/2);
    return (t*t)%big;
}
ll exp(ll x,ll y){
    if(y==0)return 1;//0^0=1
    if(x==1||y==0)return x;
    if(y%2==1)return exp(x,y-1)*x;
    ll t=exp(x,y/2);
    return t*t;
}
ll inv(ll x){
    return expm(x,big-2);
}


int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(10);
    /*--------------------------------*/

    int a,b,c;cin >> a >> b >> c;
    if(a+b==c||a+c==b||b+c==a)cout << "Yes";
    else cout << "No" ;
    cout << endl;
}

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

class Dice{
    public:
    int f[6];
    Dice(){};
    void rollS(){roll(0,1,5,4);}
    void rollE(){roll(0,2,5,3);}
    void rollR(){roll(1,2,4,3);}
    void roll(int a, int b, int c, int d){
        int e = f[a]; f[a] = f[b]; f[b] = f[c]; f[c] = f[d]; f[d] = e;
    }
};

bool check(Dice d1,Dice d2){
    for (int i = 0; i < 6; i++){
        if (d1.f[i] != d2.f[i]) return false;
    }
    return true;
}

bool fullcheck(Dice d1, Dice d2){
    int A = 0;
    for (int i = 0; i < 6; i++){
        for (int j = 0; j < 4; j++){
            if (check(d1,d2)) return true;
            d1.rollR();
        }
        if (i % 2 == 0) d1.rollS();
        else d1.rollE();
    }
    return false;
}

int main(){
    Dice d1, d2;
    for (int i = 0; i < 6; i++){
        cin >> d1.f[i];
    }
    for (int i = 0; i < 6; i++){
        cin >> d2.f[i];
    }
    if (fullcheck(d1,d2)) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}



Measured memory_bytes: 3100
#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <list>
#include <cstring>
#include <stack>
   
using namespace std;

#define mod 1000000007

int n;
int p[41], t[41];

pair<bool, int> solve()
{
    if(p[1] > t[1]) return make_pair(false, 1);
    int result[41][4];
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= 3; j++){
            result[i][j] = mod;
        }
    }
    result[1][1] = p[1];
    for(int i = 1; i < n; i++){
        int limtime = t[i + 1] - t[i];
        int length = abs(p[i + 1] - p[i]);
        for(int j = 1; j < 4; j++){
            if(j < 3 && length * (j + 1) <= limtime) result[i + 1][j + 1] = min(result[i][j] + length, result[i + 1][j + 1]);
            if(p[i] * (j + 1) + p[i + 1] <= limtime) result[i + 1][1] = min(result[i][j] + p[i] + p[i + 1] ,result[i + 1][1]);
        }
    }
    for(int i = 1; i <= n; i++){
        int mint = mod;
        for(int j = 1; j < 4; j++){
            mint = min(mint, result[i][j]);
            // cout << result[i][j] << " ";
        }
        if(mint == mod) return make_pair(false, i);
        // cout << endl;
    }
    return make_pair(true, min(result[n][1], min(result[n][2], result[n][3])) + p[n]);
}

int main()
{
    while(1){
        cin >> n;
        if(n == 0) break;
        for(int i = 1; i <= n; i++){
            cin >> p[i] >> t[i];
        }
        pair<bool, int> ans = solve();
        if(ans.first) cout << "OK ";
        else cout << "NG ";
        cout << ans.second << endl;
    }
}

Measured memory_bytes: 3052
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define FORR(I,A,B) for(ll I = (B-1); I >= (A); --I)
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
const ll INF=1e18+7;
const ll MOD=1e9+7;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n;
	cin >> n;
	cout << n << ":";
	vector<ll> ans;
	ll k = n;
	FOR(i,2,sqrt(k)+1){
		while(n%i==0){
			n/=i;
			ans.push_back(i);
		}
	}
	if(ans.size()==0){
		cout << " " << k << endl;
	}else{
		FOR(i,0,ans.size())cout << " " << ans[i];
		if(n!=1)cout << " " << n;
		cout << endl;
	}
}


Measured memory_bytes: 3240
#include<bits/stdc++.h>
using namespace std;
int main(){
	int K,A,B; cin>>K>>A>>B;
	for(int i=A;i<=B;i++){
		if(i%K==0) {
			cout<<"OK"<<'\n'; 
			return 0;
		}
	}
	cout<<"NG"<<'\n';
	return 0;
}

Measured memory_bytes: 3620
import sys
readline = sys.stdin.readline
from collections import deque
INF = 10 ** 4
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def main():
    H, W = map(int, readline().rstrip().split())
    mat = [readline().rstrip() for _ in range(H)]
    maze = [[INF] * W for _ in range(H)]
    maze[0][0] = 0
    que = deque([(0, 0)])
    flg = True
    while que and flg:
        h, w = que.popleft()
        for dh, dw in directions:
            if 0 <= h+dh < H and 0 <= w+dw < W:
                if mat[h+dh][w+dw] == '.' and maze[h+dh][w+dw] > maze[h][w] + 1:
                    maze[h+dh][w+dw] = maze[h][w] + 1
                    que.append((h+dh, w+dw))
                if h+dh == H-1 and w+dw == W-1:
                    flg = False

    if maze[H-1][W-1] == INF:
        print(-1)
    else:
        cnt_b = sum([l.count('#') for l in mat])
        print(H * W - cnt_b - (maze[H-1][W-1] + 1))

if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll INF = 1LL << 62;
const int inf = 1 << 30;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int A, B, C; cin >> A >> B >> C;
    string res = "NO";
    rep(y, 123456){
        if((B * y + C) % A == 0){
            res = "YES";
            break;
        }
    }
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
    char s[256];

    int N;
    scanf("%d", &N);

    char S[N], T[N];
    scanf("%s %s", S, T);

    for (int i = 0; i <= N; i++) {
        s[2 * i] = S[i];
        s[2 * i + 1] = T[i];
    }

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

Measured memory_bytes: 128
import java.util.*;
import java.lang.*;

public class Main {
    
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        String s = sc.next();

        String ans = "";
        
        for (int i = 0; i < n; i++) {
            //System.out.println(s.charAt(i));
            if (i == k - 1) {
                ans += Character.toLowerCase(s.charAt(i));
                //System.out.println(Character.toLowerCase(s.charAt(i)));
            } else {
                ans += s.charAt(i);
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 23252
// Aizu 2490: Parentheses
// 2017.9.25 bal4u@uu

#include <stdio.h>

int main()
{
	int n, x, ans;
	char p[10];

	scanf("%d", &n); ans = 0;
	while (n-- > 0) {
		scanf("%s%d", p, &x);
		if (*p == '(') ans += x;
		else           ans -= x;
		if (ans < 0) { puts("NO"); return 0; }
	}
	puts(ans == 0 ? "YES" : "NO");
	return 0;
}

Measured memory_bytes: 1816
#include <bits/stdc++.h>
#define MAX 10000007
using namespace std;
 
int main()
{
	
	long int i,j,count=0,x;
	vector<long int> prime;
	prime.assign(MAX, 1);
	

	prime[0] = prime[1] = false;
	
	for(i=2;i<MAX;i++)
	{
		if(prime[i] == false);
		else{
			for(j=2*i;j<MAX;j+=i)
			{
				prime[j] = false;
			}
		}
	}
	
	scanf("%ld", &x);
	
	while(1)
	{
		if(prime[x] == 1)
		{
			printf("%ld",x);
			return 0;
		}
		else x++;
	}
}

Measured memory_bytes: 81212
#include<bits/stdc++.h>
using namespace std;
// -----------------<fast IO>------------------
#define IOS             ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FLSH             fflush(stdout)
#define fileIO(name) \
    freopen(name".in", "r", stdin); \
    freopen(name".out", "w", stdout);
#define PRECISION(x)     cout << fixed << setprecision(x);
// -----------------<TypeDef Start>------------------
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
// -----------------<Constants>------------------
const int MAXN = 1000005;
const int SQRTN = 1003;
const int LOGN = 22;
const double PI=acos(-1);

const int INF=1e9;

int MOD = 1000000007;
const int FMOD = 998244353;
const double eps = 1e-9;
/*ll gcd(ll a,ll b)
{
    if(a==0)
    return(b);
    return(gcd(b%a,a));
}*/
// --------------------------------------------------</TEMPLATE>--------------------------------------------------

long double dp[3000][3000];
void solve()
{
    ll n;
    cin>>n;
    long double arr[n];
    for(ll i=0;i<n;i++)
        cin>>arr[i];
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            if(j==0)
                dp[i][j]=dp[i-1][j]*((long double)1-arr[i-1]);
            else
                dp[i][j]=dp[i-1][j-1]*arr[i-1]+dp[i-1][j]*((long double)1-arr[i-1]);
        }
    }
    long double ans=0;
    for(int i=n/2+1;i<=n;i++)
        ans+=dp[n][i];
    cout<<fixed<<setprecision(10)<<ans<<endl;
}

int main()
{
    IOS
    ll t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return(0);
}


Measured memory_bytes: 144460
//                             In The Name Of Allah                                           
//                             	Mohammad Hosseini
#include <bits/stdc++.h>
#define	ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define pb push_back
#define int long long
#define ld long double
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std; 

const int N = 3e5 + 100, OO = 724249387, T = 4500 + 100, M = 1e9 + 7, P = 6151, SQ = 280, lg = 30;
typedef pair <int, int> pii;

int32_t main() {
	use_fast;
	int n, x;
	cin >> n >> x;
	int t = __gcd(n, x);
	cout << 3 * (n - t);
    return 0;
}
/*
be carefull :
1- if not solve after 20 min, read again twice
2- after submit read the code again
3- fun with contest
4- uploaded by ubuntu 20.04 
5- ...
*/



Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PLL> VP;
typedef vector<ll> VLL;
#define rep(i,n) for (ll i=0; i<(ll)(n); i++)
#define repd(i,n) for (ll i=n-1; i>=0; i--)
#define rept(i,m,n) for(ll i=m; i<n; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define PF push_front
#define PB push_back
#define SORT(V) sort((V).begin(), (V).end())
#define RVERSE(V) reverse((V).begin(), (V).end())
#define paired make_pair
#define PRINT(V) for(auto v : (V)) cout << v << " "

int main()
{
    ll M, N;
    cin >> M >> N;
    if(M==2 || N==2){
        cout << 0 << endl;
        return 0;
    }
    if(N==1 && M>=3){
        cout << M-2 << endl;
        return 0;
    }
    if(M==1 && N>=3){
        cout << N-2 << endl;
        return 0;
    }
    if(M==1 && M==1){
        cout << 1 << endl;
        return 0;
    }
    else{
        cout << (M-2)*(N-2) << endl;
    }
}

Measured memory_bytes: 256
// template
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<long long, long long> LP;
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define REP_AB(i, a, b) for (ll i = ll(a); i < ll(b); i++)
#define REP_IN(i, n, x) for (ll i = 0; i < n; i++)in>>x;
#define REP_OUT(i, n, x) for (ll i = 0; i < n; i++)out<<x<<endl;
#define ALL(v) v.begin(), v.end()
#define SORT(v) sort(ALL(v))
#define UNIQUE(v) sort(ALL(v));v.erase(unique(ALL(v)), v.end());
#define SIZE(x) ((ll)(x).size())
#define REVERSE(v) reverse(ALL(v))
// true / false
#define BIN_SEARCH(v, a) binary_search(ALL(v), a)
// index
#define BIN_LEFT(v, a) (lower_bound(ALL(v), a) - v.begin())
#define BIN_RIGHT(v, a) (upper_bound(ALL(v), a) - v.begin())
#define BIN_INSERT(v, a) (v.insert(v.begin() + BIN_LEFT(v, a), a))
#define DEL(v, i) v.erase(v.begin() + i)
#define INSERT(v, i, a) v.insert(v.begin() + i, a)
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;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
#define out cout
#define in cin
#define endl '\n'
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; }
// template end
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll N, ans = 0;
    in >> N;
    
    //c = ceil(N/2.0);
    /*
    REP_AB(i, ceil(N/2.0)-1, N){
        ans += c;
        c++;
    }
    */
   /*
   if(N%2==1){
       REP(i ,ceil(N/2.0)-1){
           ans += i + N-i-1;
       }
       ans += ceil(N/2.0)-1;
   }else{
       REP(i ,ceil(N/2.0)){
           ans += i + N-i-1;
       }
   }
   */

   REP(i, N){
       ans += N-i-1;
   }
   
    /*
    REP(i, N){
        ans += i;
    }
    */
    out << ans << endl;


}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;
ll MOD=1000000007;
ll powMOD(ll x,ll y){
    ll res=1;
    rep(i,y) res=res*x%MOD;
    return res;
}
int main(){
    ll n;
    cin>>n;
cout<<((powMOD(10,n)-2*powMOD(9,n)+powMOD(8,n))%MOD+MOD)%MOD;
  return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <array>
#include <string>

bool solve(const std::string &w)
{
	std::array<unsigned, 26> a;
	for(unsigned i=0; i<26; ++i)
	{
		a[i] = 0;
	}
	
	for(auto &c : w)
	{
		++a[c - 'a'];
	}
	
	for(unsigned i=0; i<26; ++i)
	{
		if(a[i] % 2 != 0)
		{
			return false;
		}
	}
	
	return true;
}

int main()
{
	std::string w;
	std::cin >> w;
	
	std::cout << (solve(w) ? "Yes" : "No") << std::endl;
	
	return 0;
}

Measured memory_bytes: 256
def main():
    # n = int(input())
    n, m = map(int, input().split())
    # a = list(map(int, input().split()))
    # s = input()
    # h = [int(input()) for _ in rane(n)]

    ab = []
    for i in range(n):
        a, b = map(int, input().split())
        ab.append([a, b])

    cost = 0
    temp_i = 0
    ab.sort(key=lambda x: x[0])
    for i in range(n):
        cost += ab[i][0] * ab[i][1]
        m -= ab[i][1]
        if m <= 0:
            temp_i = i
            break

    if m == 0:
        print(cost)
    elif m < 0:
        cost += ab[temp_i][0] * m
        print(cost)


if __name__ == '__main__':
    main()


Measured memory_bytes: 92508
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;

#define lengthof(x) (sizeof(x) / sizeof(*(x)))
struct edge { int to, cost; };
typedef pair<int, int> P;

const int INF = (int)1e9;
int N, M, R;
int dist[8][8];
vector<vector<edge> > G;
vector<int> d;
vector<int> Q;

void dijkstra(int s) {
	priority_queue<P, vector<P>, greater<P> > que;
	d.clear();
	d.resize(N, INF);
	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;
		for (int i = 0; i < (int)G[v].size(); ++i) {
			edge e = G[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

void calcu_dist(void) {
	fill((int*)dist, (int*)(dist + lengthof(dist)), INF);
	for (int i = 0; i < R - 1; ++i) {
		dijkstra(Q[i]);
		for (int j = i + 1; j < R; ++j) {
			int dst = d[Q[j]];
			dist[i][j] = dist[j][i] = dst;
		}
	}
}

int solve(void) {
	int min_cst = INF;
	vector<int> vi(R);
	for (int i = 0; i < R; ++i)
		vi[i] = i;
	do {
		int cst = 0;
		for (int i = 0; i < R - 1; ++i)
			cst += dist[vi[i]][vi[i + 1]];
		min_cst = min(min_cst, cst);
	} while (next_permutation(vi.begin(), vi.end()));

	return min_cst;
}

int main(void) {
	cin >> N >> M >> R;
	Q.resize(R);
	for (int i = 0; i < R; ++i) {
		int r;
		cin >> r;
		Q[i] = r - 1;
	}
	G.resize(N);
	for (int i = 0; i < M; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		edge ed;
		ed.cost = c;
		ed.to = b - 1;
		G[a - 1].push_back(ed);
		ed.to = a - 1;
		G[b - 1].push_back(ed);
	}

	calcu_dist();
	int ans = solve();

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


Measured memory_bytes: 640
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>

std::vector<int> count(std::string s, std::vector<int> v); 
void print(std::vector<int> v); 

int main(void) {
    std::string s;
    std::vector<int> v(26, 0);

    while (std::getline(std::cin, s)) {
        int len = (int)(s.length());
        v = count(s, v);
    }
    print(v);
    return EXIT_SUCCESS;
}

std::vector<int> count(std::string s, std::vector<int> v) {
    int len = (int)(s.length());
    int diff = int('a') - int('A');
    for (int i = 0; i < len; i++) {
        if ((int)(s[i]) >= int('A') && (int)(s[i]) <= int('Z')) {
            s[i] += diff;
        }
        if ((int)(s[i]) >= int('a') && (int)(s[i]) <= int('z')) {
            v[(int)(s[i])-(int)('a')] ++;
        }
    }
    return v;
}

void print(std::vector<int> v) {
    int size = (int)(v.size());
    for (int i = 0; i < size; i++) {
        char word = (char)((int)('a')+i);
        std::cout << word << " : " << v[i] << std::endl;
    }
}

Measured memory_bytes: 3124
#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

int main(){
	int n;
  	cin >> n;
  
  	ll ar[n];
  
  	for(int i = 0; i < n; i++){ cin >> ar[i]; }
  
  	sort(ar, ar+n);
  	reverse(ar, ar+n);
  	
  	ll total = 0;
  	for(int i = 1; i <  n; i++){ total += ar[i/2]; }
  
  	cout << total << endl;
  
  	return 0;
}

Measured memory_bytes: 5180
from heapq import heapify, heappush, heappop

x,y,a,b,c = map(int, input().split())
red = list(map(int, input().split()))
green = list(map(int, input().split()))
transparence = list(map(lambda x: -int(x), input().split()))

red.sort(reverse=True)
green.sort(reverse=True)
heapify(transparence)

L = []

for i in range(min(a, x)):
    heappush(L, red[i])
for i in range(min(0, x-a)):
    item = heappop(transparence)
    heappush(L, -item)


for i in range(min(b, y)):
    heappush(L, green[i])
for i in range(min(0, y-b)):
    item = heappop(transparence)
    heappush(L, -item)

while True:
    if len(transparence)<= 0:
        break
    item = heappop(transparence)
    min_L = heappop(L)
    if min_L < -item:
        heappush(L, -item)
    else:
        heappush(L, min_L)
        break


print(sum(L))




Measured memory_bytes: 121708
#include<stdio.h>
int main(void){
    int n,m,l,i,j,k;
    int a[101][101], b[101][101];
	long c[101][101];
    scanf("%d%d%d",&n,&m,&l);
    for(i=0; i<n; i++){
        for(j=0; j<m; j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(i=0; i<m; i++){
        for(j=0; j<l; j++){
            scanf("%d",&b[i][j]);
        }
    }
    for(i=0; i<n; i++){
        for(j=0; j<l; j++){
            c[i][j]=0;
            for(k=0; k<m; k++){
                c[i][j]+=a[i][k]*b[k][j];
            }
        }
    }
    for(i=0; i<n; i++){
        for(j=0; j<l; j++){
            printf("%ld",c[i][j]);
            if(j!=l-1) printf(" ");
        }
        putchar('\n');
    }
    return 0;
} 


Measured memory_bytes: 2112
from fractions import gcd


def lcm(x, y):
    return x * y // gcd(x, y)


a, b, c, d = map(int, input().split())

cnt_b = b // c + b // d - b // lcm(c, d)
cnt_a = (a - 1) // c + (a - 1) // d - (a - 1) // lcm(c, d)

print(b - a + 1 - (cnt_b - cnt_a))

Measured memory_bytes: 5372
#include<stdio.h>
char c;
char d[4];
int main(void){
  while((c=getchar())!=10){
    if(c=='N'){
      d[0]=1;
    }else if(c=='W'){
      d[1]=1;
    }else if(c=='S'){
      d[2]=1;
    }else{
      d[3]=1;
    }
  }
  if((d[0]^d[2]) || (d[1]^d[3])){
    puts("No");
  }else{
    puts("Yes");
  }
}


Measured memory_bytes: 128
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

void main() {
    readint;
    auto ab = readints;
    int a = ab[0], b = ab[1];
    auto ps = readints;

    auto n1 = ps.count!(e => e <= a);
    auto n2 = ps.count!(e => a < e && e <= b);
    auto n3 = ps.count!(e => e > b);
    writeln(min(n1, n2, n3));
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    int i,N;
    
    scanf("%d",&N);
    
    if(N % 10 == 9){
        printf("Yes");
    }else if(N >= 90 && N <= 99){
        printf("Yes");
    }else{
        printf("No");
    }
    return 0;
}


Measured memory_bytes: 128
import math
K = int(input())

temp_list = []
temp_list_2 = []
for i in range(1, K+1):
    for j in range(1, K+1):
        temp_list.append(math.gcd(i, j))
for i in range(1, K+1):
    for j in temp_list:
        temp_list_2.append(math.gcd(i, j))
print(sum(temp_list_2))


Measured memory_bytes: 71760
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = input()
t = []
for i in range(n):
    if s[i] == 'o':
        t.append(0)
    else:
        t.append(1)
def chk():
    if res[n-1] ^ t[n-1] != res[0] ^ res[n-2]:
        return False
    if res[0] ^ t[0] != res[n-1] ^ res[1]:
        return False
    return True
for zero,one in itertools.product(range(2),repeat=2):
    # 0:S 1:W
    res = [0] * n
    res[0] = zero; res[1] = one
    for i in range(2,n):
        if res[i-1] == t[i-1]:
            res[i] = res[i-2]
        else:
            res[i] = res[i-2]^1
    if chk():
        ans = []
        for i in range(n):
            ans.append('W' if res[i] else 'S')
        print(''.join(ans))
        quit()
print(-1)


Measured memory_bytes: 13356
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main()
{
    string s[3];
    for(int i=0;i<3;i++){
        cin>>s[i];
    }
    char top{},ans{};
    while(true){
        if(s[top].empty()){
            ans=top;
            break;
        }
        int next;
        if(s[top][0] == 'a'){
            next = 0;
        }else if(s[top][0] == 'b'){
            next = 1;
        }else if(s[top][0]=='c'){
            next = 2;
        }
        s[top] = s[top].substr(1);
        top = next;
    }
        if(ans==0)cout<<"A"<<endl;
    else if(ans==1)cout<<"B"<<endl;
    else cout<<"C"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <complex>

#define forin(i, f, t) for(auto i = f; i < t; i++)

using namespace std;
using ll = long long;

int main() {
    string s;
    cin >> s;
    ll omg;
    cin >> omg;
    
    for (auto i = 0; i < s.size(); i += omg)
        cout << s[i];
    
    
    return 0;
}



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

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

pair<int,int> ans[111111];
int tosi[111111];
vector<pair<pair<int,int>,int>> v;

int main(){

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

	REP(i,m){
		int a,b;cin >> a >> b;
		v.PB(MP(MP(b,a),i));
	}

	sort(ALL(v));

	REP(i,v.size()){
		tosi[v[i].FI.SE]++;
		ans[v[i].SE] = MP(v[i].FI.SE,tosi[v[i].FI.SE]);
	}

	REP(i,m){
		printf("%06d%06d\n",ans[i].FI,ans[i].SE);
	}


	return 0;
}


Measured memory_bytes: 4084
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define Graph vector<vector<ll>>
#define INF (1ll<<60)
#define mod 1000000007
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; }

int main(){
    ll n;cin>>n;
    if(n%1000==0){
        cout<<0<<endl;
        return  0;
    }
    cout<<1000*(n/1000+1)-n<<endl;
    return 0;
}


Measured memory_bytes: 3668
W, H, N = gets.split.map{|i|i.to_i}
grid = Array.new(H){Array.new(W){true}}
N.times{
    x, y, a = gets.split.map{|i|i.to_i}
    case a
    when 1
        H.times{|r|
            (0...x).each{|c|
                grid[r][c] = false
            }
        }
    when 2
        H.times{|r|
            (x...W).each{|c|
                grid[r][c] = false
            }
        }
    when 3
        (0...y).each{|r|
            W.times{|c|
                grid[r][c] = false
            }
        }
    when 4
        (y...H).each{|r|
            W.times{|c|
                grid[r][c] = false
            }
        }
    end
}
puts grid.inject(0){|r, i|r + i.count(true)}


Measured memory_bytes: 3964
import sys
input = sys.stdin.readline
N = int(input())
def inputs():return [int(x) for x in input().split()]
f = [inputs() for _ in range(N)]
p = [inputs() for _ in range(N)]
cnt =[0]*(N)
ans = -10**9
for bit in range(1,1<<10):
    ans1 = 0
    cnt =[0]*(N)
    for j in range(10):
        for i in range(N):
            if bit&1<<j and f[i][j]==1:
                cnt[i] +=1
    ans1 += sum([p[i][cnt[i]] for i in range(N)])
    ans = max(ans1,ans)
print(ans)


Measured memory_bytes: 42604
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	return x*f;
}
const int N=2e5+7,INF=1e9;
int n,ans;
struct dat {
	int l,r;
	dat (int _l=0,int _r=0) { l=_l,r=_r; }
	inline bool operator < (const dat &tmp) const {
		return l!=tmp.l ? l<tmp.l : r<tmp.r;
	}
}d[N];
int lx[N],rx[N],ly[N],ry[N];
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
		d[i].l=read(),d[i].r=read();
	sort(d+1,d+n+1);
	lx[1]=d[1].l,rx[1]=d[1].r;
	for(int i=2;i<=n;i++)
	{
		lx[i]=max(lx[i-1],d[i].l);
		rx[i]=min(rx[i-1],d[i].r);
	}
	ly[n]=d[n].l; ry[n]=d[n].r;
	for(int i=n-1;i>=1;i--)
	{
		ly[i]=max(ly[i+1],d[i].l);
		ry[i]=min(ry[i+1],d[i].r);
	}
	for(int i=1;i<n;i++)
		ans=max(ans,max(0,rx[i]-lx[i]+1)+max(0,ry[i+1]-ly[i+1]+1));
	for(int i=1;i<=n;i++)
		ans=max(ans,d[i].r-d[i].l+1+max(0 , min(ry[i+1],rx[i-1])-max(ly[i+1],lx[i-1])+1 ));
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define All(v) (v).begin(),(v).end()
int dy[8] = {-1,0,1,0,-1,1,1,-1};
int dx[8] = {0,1,0,-1,1,1,-1,-1};
const int mod = 1000000007;
const int inf = mod*mod;
const int d5 = 100100;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a,b,c,k;
    cin>>a>>b>>c>>k;
    int res=min(a,k);
    k-=a;
    if(k>0)k-=b;
    if(k>0)res-=min(c,k);
    cout<<res<<endl;
}

Measured memory_bytes: 3656
import sys
sys.setrecursionlimit(1000000)

n = int(input())
action = []
for i in range(n):
    action.append(list(map(int,input().split())))

memo = []
for i in range(n):
    memo.append([-1]*3)

def dp(i, a):
    if i == 0:
        return action[0][a]
    elif memo[i][a] != -1:
        return memo[i][a]
    else:
        memo[i][a] = max(dp(i-1, (a+1)%3), dp(i-1, (a+2)%3)) + action[i][a]
        return memo[i][a]

print(max([dp(n-1,a) for a in range(3)]))

Measured memory_bytes: 122584
#define _USE_MATH_DEFINES

#include <iostream>	//cin, cout
#include <vector>	//vector
#include <algorithm> //sort,min,max,count
#include <string>	//string,getline
#include <ios>		//fixed
#include <iomanip>	//setprecision
#include <utility> //swap
#include <cstdlib>	//abs(int)
#include <cmath>	//sqrt
#include <sstream>	//stringstream,getline
#include <cmath>	//ceil,M_PI
#include <numeric>	//gcd
#include <deque>	//deque

using namespace std;

int main() {

	int N;
	cin >> N;

	double ans = 0;

	if (N % 2 == 0) {
		cout << "0.5000000000" << endl;
	}
	else {
		ans = ((N + 1) / 2.0) / N;
		cout << fixed << setprecision(15) << ans << endl;
	}

	return 0;

}

Measured memory_bytes: 3760
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
using namespace std;
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();}
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EACH(t,i,c) for(t::iretator i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,n-1)
const double EPS = 1e-10;
const double PI = acos(-1.0);

#include <complex>
typedef complex<double> P;

struct L {
	P a, b;
	L(const P &a, const P &b) : a(a), b(b) { }
};

struct C {
	P p; double r;
	C(const P p, double r) : p(p), r(r) { }
};

double dot(P a, P b) {
	return real(conj(a)*b);
}

double cross(P a, P b) {
	return imag(conj(a)*b);
}

bool LLcross(L l1, L l2) {
	return abs(cross(l1.b-l1.a, l2.b-l2.a)) > EPS || abs(cross(l1.b-l1.a, l2.b-l1.a)) < EPS;
}

double dist(P p1, P p2) {
	return sqrt((p2.real()-p1.real())*(p2.real()-p1.real()) + (p2.imag()-p1.imag())*(p2.imag()-p1.imag()));
}

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

	REP(i, n) {
		double x, y, r;
		cin >> x >> y >> r;
		C c1(P(x, y), r);

		cin >> x >> y >> r;
		C c2(P(x, y), r);

		double d = dist(c1.p, c2.p);
		int ans;
		
		if(c2.r-d-c1.r > EPS) {
			ans = -2;
		} else if (c1.r-d-c2.r > EPS){
			ans = 2;
		} else if (d-c2.r-c1.r < EPS) {
			ans = 1;
		} else {
			ans = 0;
		}

		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 1232
#include <bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(0); cin.tie(); cout.tie();

#define MAXX 500005
#define PI 3.14159265358979323846264338327950
#define F first
#define S second
#define ll  long long int
#define mod  1000000007



int main()
{
	FAST;
	ll n;
	double a, b;
	cin >> n >> a >> b ;
	double mn = a;
	vector< pair <double , int> > v; 
	for(ll i = 1; i <= n; i ++){
		double f;
		cin >> f;
		double x = a - (f * 0.006);
		x = abs(b - x);
		v.push_back( {x, i} );
	}
	sort(v.begin(), v.end());
	cout << v[0].second;
	
}

Measured memory_bytes: 3792
#include<stdio.h>
#include<string.h>
int N,M,G[100],i,j,k,L[100],S,E,R;
int dp[1<<18];
int main()
{
	for(;scanf("%d",&N),N;)
	{
		memset(G,0,sizeof(G));
		for(i=0;i<N;i++)
		{
			
			scanf("%d%d",&M,&L[i]);
			for(j=0;j<M;j++)
			{
				scanf("%d%d",&S,&E);
				S-=6;E-=6;
				G[i]|=((1<<E)-1)-((1<<S)-1);
			}
		}
		memset(dp,-1,sizeof(dp));
		dp[0]=R=0;
		for(i=0;i<(1<<18);i++)
		{
			if(dp[i]==-1)continue;
			for(j=0;j<N;j++)
				if((i&G[j])==0&&dp[i|G[j]]<dp[i]+L[j])
				{
					dp[i|G[j]]=dp[i]+L[j];
					R=R<dp[i]+L[j]?dp[i]+L[j]:R;
				}
		}
		printf("%d\n",R);
	}
	return 0;
}

Measured memory_bytes: 1632
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(i) for i in input().split()))
    C.append(sum(1<<(int(i)-1) for i in input().split()))

INF = 10**18
# dp[i]: 状態がbin(i)のときの費用の最小値
# bin(i)のj桁が1: j番目の宝箱を開けられる
# 1<<N == 2**N
dp = [INF] * (1<<N)

# 初期条件(全ての宝箱を開けられない)
dp[0] = 0

for i in range(1<<N):
    for (a,b),c in zip(AB,C):
        # 状態iで状態cにする鍵を買ったときの状態
        state = i | c
        dp[state] = min(dp[state], dp[i]+a)

answer = dp[-1]
if answer == INF:
    answer = -1
print(answer)

Measured memory_bytes: 42476
#include<bits/stdc++.h>
#define ll long long
//#define MOD int(1e9+7)
#define pb push_back
using namespace std;

int M=int(1e9+7);         //   pow(x,y,m)
long long int power(long long int x, long long int y)
{
    if (y == 0) return 1;
    if (y%2 == 1) return (x*power(x, y-1))%M;
    long long int t = power(x, y/2);
    return (t*t)%M;
}

int prime[1000003];
unordered_map<int, int> max_map;

// Function to find the smallest prime factors
// of numbers upto 1000003
void sieve()
{
    prime[0] = prime[1] = 1;
    for (int i = 2; i < 1000003; i++) {
        if (prime[i] == 0) {
            for (int j = i * 2; j < 1000003; j += i) {
                if (prime[j] == 0) {
                    prime[j] = i;
                }
            }
            prime[i] = i;
        }
    }
}

// Function to return the LCM modulo M
ll lcmModuloM(vector<ll>& ar, int n)
{

    for (int i = 0; i < n; i++) {
        int num = ar[i];
        unordered_map<int, int> temp;

        // Temp stores mapping of prime factor to
        // its power for the current element
        while (num > 1) {

            // Factor is the smallest prime factor of num
            int factor = prime[num];

            // Increase count of factor in temp
            temp[factor]++;

            // Reduce num by its prime factor
            num /= factor;
        }

        for (auto it : temp) {

            // Store the highest power of every prime
            // found till now in a new map max_map
            max_map[it.first] = max(max_map[it.first], it.second);
        }
    }

    ll ans = 1;

    for (auto it : max_map) {

        // LCM is product of primes to their highest powers modulo M
        ans = (ans * power(it.first, it.second)) % M;
    }

    return ans;
}

int main()
{
    sieve();
    ll n;
    cin>>n;
    vector<ll> v(n);
    for(int i=0;i<n;i++) cin>>v[i];

    ll l=lcmModuloM(v,n),p=0;
    for(int i=0;i<n;i++) p=(p+power(v[i],M-2))%M;

    cout<<(l*p)%M;
}



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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

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

  int n, k;
  cin >> n >> k;
  vector<int> ps(n);
  for (int i = 0; i < n; i++) {
    cin >> ps[i];
  }

  int l = 0;
  int r = 0;
  set<int> s1;  // Window
  set<int> s2;  // Active window

  set<tuple<int, int>> pairs;

  for (int i = 0; i < k; i++) {
    if (s1.empty()) {
      s1.insert(ps[i]);
    } else {
      int s1_max = *s1.rbegin();
      if (s1_max > ps[i]) {
        for (int j = r; j < i + 1; j++) {
          s2.insert(ps[j]);
        }
        r = i + 1;
        // Update l
        while (!s2.empty() && ps[l] == *s2.begin()) {
          s2.erase(ps[l]);
          l++;
        }
      }
      s1.insert(ps[i]);
    }
  }
  if (DEBUG) cout << "l: " << l << " r: " << r << endl;
  if (l == r) {
    pairs.insert(make_tuple(0, 0));
  } else {
    pairs.insert(make_tuple(l, r));
  }

  for (int i = k; i < n; i++) {
    s1.erase(ps[i - k]);
    s2.erase(ps[i - k]);
    if (l == i - k) l++;
    if (l > r) r = l;

    int s1_max = *s1.rbegin();
    if (s1_max > ps[i]) {
      for (int j = r; j < i + 1; j++) {
        s2.insert(ps[j]);
      }
      r = i + 1;

      while (l - 1 >= i - k + 1 && ps[l - 1] > ps[i]) {
        s2.insert(ps[l - 1]);
        l--;
      }
    }
    s1.insert(ps[i]);

    // Update l
    while (!s2.empty() && ps[l] == *s2.begin()) {
      s2.erase(ps[l]);
      l++;
    }

    if (DEBUG) cout << "l: " << l << " r: " << r << endl;
    if (DEBUG) cout << "s2.size(): " << s2.size() << endl;
    if (l == r) {
      pairs.insert(make_tuple(0, 0));
    } else {
      pairs.insert(make_tuple(l, r));
    }
  }
  cout << pairs.size() << endl;
}

Measured memory_bytes: 19840
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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;
}

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}


const long long MOD = 1000000007;
const long long INF = 1LL << 60;


const int MAX_N = 100010;
int cnt[9];
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	VE a(n); rep(i, n)cin >> a[i];
	rep(i, n) {
		if (a[i] >= 3200)cnt[8]++;
		else {
			cnt[a[i] / 400] = 1;
		}
	}
	int ans = 0;
	rep(i, 8) {
		ans += cnt[i];
	}
	if(ans!=0)cout << ans << " " << ans + cnt[8] << endl;
	else cout << 1 << " " << cnt[8] << endl;
	return 0;
}


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

public static class Solution
{
    static int GetMaxChainCount(List<int>[] graph)
    {
        var max = 0;
        var n = graph.Length;
        var visited = new bool[n];

        for (int start = 0; start < n; start++)
        {
            if (visited[start])
            {
                continue;
            }

            visited[start] = true;

            var count = 1;
            var queue = new Queue<int>();
            queue.Enqueue(start);
            while (queue.Count > 0)
            {
                var cur = queue.Dequeue();
                foreach (var nei in graph[cur])
                {
                    if (!visited[nei])
                    {
                        visited[nei] = true;
                        count++;
                        queue.Enqueue(nei);
                    }
                }
            }
            max = Math.Max(max, count);
        }
        return max;
    }

    public static void Main()
    {
        var vals = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        var N = vals[0];
        var M = vals[1];
        var graph = Enumerable.Range(0, N).Select(_ => new List<int>()).ToArray();
        for (int i = 0; i < M; i++)
        {
            vals = Console.ReadLine().Split(' ').Select(x => int.Parse(x) - 1).ToArray();
            var a = vals[0];
            var b = vals[1];
            graph[a].Add(b);
            graph[b].Add(a);
        }

        var max = GetMaxChainCount(graph);
        Console.WriteLine(max);
    }
}

Measured memory_bytes: 57184
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
  
int main() {
  int A,B,C;
  cin >> A >> B >> C;
  cout << max(B + C - A,0) << endl;
  return 0;
}

Measured memory_bytes: 256