akhauriyash/Code-Regression huggingface dataset:
from copy import copy
import random
import math
import sys
input = sys.stdin.readline
D = int(input())
c = list(map(int,input().split()))
s = [list(map(int,input().split())) for _ in range(D)]
last = [0]*26
ans = [0]*D
score = 0
for i in range(D):
    ps = [0]*26
    for j in range(26):
        pl = copy(last)
        pl[j] = i+1
        ps[j] += s[i][j]
        for k in range(26):
            ps[j] -= c[k]*(i+1-pl[k])
    idx = ps.index(max(ps))
    last[idx] = i+1
    ans[i] = idx+1
    score += max(ps)
T = 300
for i in range(42000):
    na = copy(ans)
    x = random.randint(1,365)
    y = random.randint(1,365)
    if x == y:
        continue
    na[x-1],na[y-1] = na[y-1],na[x-1]
    last = [0]*26
    ns = 0
    for i in range(D):
        last[na[i]-1] = i+1
        ns += s[i][na[i]-1]
        for j in range(26):
            ns -= c[j]*(i+1-last[j])
    p = pow(math.e,-abs(ns-score)/T)
    if ns > score or random.random() < p:
        ans = na
        score = ns
    T *= 0.99
for a in ans:
    print(a)

Measured memory_bytes: 81440
import bisect

s = input()
t = input()

idx = {}
l = len(s)

for i in range(l):
  ch = s[i]
  if ch in idx:
    arr = idx[ch]
    _idx = bisect.bisect_right(arr, i + 1)
    arr.insert(_idx, i + 1)
    idx[ch] = arr
  else:
    idx[ch] = [i + 1]

ans = 0

for ch in t:
  if ch in idx:
    arr = idx[ch]
    __idx = bisect.bisect_right(arr, ans % l)
    if __idx == len(arr):
      ans = -(-ans // l) * l + arr[0]
      _idx = arr[0]
    else:
      ans = (ans // l) * l + arr[__idx]
      _idx = arr[__idx]
  else:
    ans = -1
    break

print(ans)

Measured memory_bytes: 7668
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

int main()
{
	int n,q;
	string s;
	cin >> n >> q >> s;

	vector<int> imo(n);

	bool Aflg=false;
	int cnt=0;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='A')Aflg=true;
		else
		{
			if(Aflg and s[i]=='C')
			{
				cnt++;
			}
			Aflg=false;
		}
		imo[i]=cnt;
//		cout << i << " : " << imo[i] << endl;
	}

	for(int i=0;i<q;i++)
	{
		int l,r;
		cin >> l >> r;
		l--;r--;
		cout << imo[r]-imo[l] << endl;
	}



}

Measured memory_bytes: 1408
#include <stdio.h>

int main(){

   int n, i, a[10000];
   int min = 1000000, max = -1000000; 
   long long int sum = 0;


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



   min = max = a[0];
   for (i = 0; i < n; i++) {
    if (a[i] < min) {
     min = a[i];
    }
    if (a[i] > max) {
     max = a[i];
    }

    sum = sum + a[i];
   }

   printf("%d %d %lld\n", min, max, sum);

    return  0;
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, q;
  cin >> n >> m >> q;
  auto v = vector<vector<int>>(n + 1, vector<int>(n + 1, 0));
  for (int i = 0; i < m; i++) {
    int l, r;
    cin >> l >> r;
    v[r][l]++;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i - 1; j++) {
      v[i][j + 1] += v[i][j];
    }
  }
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    int sum = 0;
    for (int i = l; i <= r; i++) {
      sum += v[i][i] - v[i][l - 1];
    }
    cout << sum << endl;
  }
  return 0;
}

Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mx 100005
#define mod 1000000007

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

    int a[n];

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

    int re=0;

    for(int i=0;i<n-1;i++)
        for(int j=i+1;j<n;j++)re+=a[i]*a[j];

    cout<<re<<endl;


    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
using namespace std;

int main() {
  int n,i,j;
  scanf("%d",&n);
  int p[n];
  for(i = 0;i<n;i++){
    scanf("%d",&p[i]);
  }
  int a;
  for(i = 0;i<n-1;i++){
    for(j = n-1;j > i;j--){
      if(p[j-1] > p[j]){
          a = p[j-1];
          p[j-1] = p[j];
          p[j] =a;
      } 
    }
  }
  a = 0;
  for(i = 0;i < n-1;i++){
    a +=p[i];
  }
  a +=(p[n-1]/2);
  printf("%d",a);
}

Measured memory_bytes: 128
#include<cstdio>
#include<cstring>
#define inlien inline
#define retrun return
#define cpnst const
bool can[1111][1111],exc[1111][1111];
inline bool ask(int x,int y)
{return can[y][x]^exc[x][y];}
int x[222222],y[222222],n,m;
#include<vector>
std::vector<int>v[1111];
bool vis[1111];
inline void dfs(int s,int p)
{
	if(vis[p])return;
	vis[p]=can[s][p]=1;
	for(register int i=0;i<v[p].size();i++)
		dfs(s,v[p][i]);
}
int frm[1111];
inline void efs(int fs,int s,int p)
{
	if(vis[p])return;vis[p]=1;
	if(frm[p])if(frm[p]^s)exc[fs][p]=1;frm[p]=s;
	for(register int i=0;i<v[p].size();i++)
		efs(fs,s,v[p][i]);
}
int main()
{
	scanf("%d%d",&n,&m);
	register int i,ii;
	for(i=1;i<=m;i++)
		scanf("%d%d",&x[i],&y[i]),v[x[i]].push_back(y[i]);
	for(i=1;i<=n;i++)
	{for(ii=1;ii<=n;ii++)vis[ii]=0;dfs(i,i);}
	for(i=1;i<=n;i++)
	{
		for(ii=1;ii<=n;ii++)vis[ii]=frm[ii]=0;vis[i]=1;
		for(ii=0;ii<v[i].size();ii++)efs(i,v[i][ii],v[i][ii]);
		for(ii=1;ii<=n;ii++)vis[ii]=0;vis[i]=1;
		for(ii=v[i].size()-1;~ii;ii--)efs(i,v[i][ii],v[i][ii]);
	}for(i=1;i<=m;i++)puts(ask(x[i],y[i])?"diff":"same");
}
/*
Giving the world a better yourself is giving yourself a better world. 
*/

Measured memory_bytes: 6656
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c;
  cin>>a>>b>>c;
  int x;
  bool flag=false;
  for(int t=0; t<=100; t++){
    for(int k=0; k<=10000; k++){
      if(0<=60*t+c-(a+b)*k&&60*t+c-(a+b)*k<=a){
      x=t,flag=true;
      goto end;
      }
    }
  }
  end:
  if(flag){cout<<60*x+c<<endl;}
  else cout<<-1<<endl;
}


Measured memory_bytes: 3096
#include "bits/stdc++.h"
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define all(V) (V).begin(), (V).end()
using namespace std;
typedef long long ll;

int main() {fio;
	string s;
	ll K;
	cin >> s >> K;
	ll tot = 0;
	if(count(all(s), s[0]) == s.size()) {
		ll h = s.size() * K;
		cout << h / 2;
 		return 0;
	}
	string f;
	for(int i = 0; i < s.size(); i++) {
		if(s[(i + 1) % s.size()] == s[i]) {
			continue;
		} else {
			for(int j = 0; j < s.size(); j++) {
				f += s[(i + 1 + j) % s.size()];
			}
			break;
		}
	}
	ll y = 0, x = 0;
	int cur = 1;
	for(int i = 1; i < f.size(); i++) {
		if(f[i] == f[i - 1]) {
			cur++;
		} else {
			y += cur / 2;
			cur = 1;
		}
	}
	y += cur / 2;
	cur = 1;
	for(int i = 1; i < s.size(); i++) {
		if(s[i] == s[i - 1]) {
			cur++;
		} else {
			x += cur / 2;
			cur = 1;
		}
	}
	x += cur / 2;
	cout << y * (K - 1) + x;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <utility>
#include <algorithm>
#include <functional>
#include <deque>
#define INF 1e9
#define MAX_H 301
#define MAX_W 301
#define MAX_Q 100001

using namespace std;

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

int main() {
    int H, W, D;
    cin >> H >> W >> D;
    P B[MAX_H * MAX_W];
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            int a;
            cin >> a;
            B[a] = make_pair(i, j);
        }
    }
    
    int sum[MAX_H * MAX_W];
    for (int i = 1; i <= D; ++i) {
        sum[i] = 0;
    }
    for (int i = 1; i <= D; ++i) {
        for (int k = 0; i + (k+1) * D <= H * W; ++k) {
            int cur = i + k * D;
            int nxt = cur + D;
            int c = abs(B[cur].first - B[nxt].first) + abs(B[cur].second - B[nxt].second);
            sum[nxt] = sum[cur] + c;
        }
    }
    
    int Q;
    cin >> Q;
    int L[MAX_Q], R[MAX_Q];
    for (int i = 0; i < Q; ++i) {
        cin >> L[i] >> R[i];
    }
    for (int i = 0; i < Q; ++i) {
        int l = L[i], r = R[i];
        int ans;
        if (l < r) {
            ans = sum[r] - sum[l];
        } else if (l > r) {
            ans = sum[l] - sum[r];
        } else {
            ans = 0;
        }
        cout << ans << endl;
    }
    return 0;
}


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

int main()
{
    int L,R,d;
    int count=0;
    int i;
    scanf("%d%d%d",&L,&R,&d);
    for(i=L;i<R+1;i++)
    {
        if((i>d||i==d)&&(i%d==0))
            count++;
    }
    printf("%d",count);
    return 0;
}


Measured memory_bytes: 2060
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int MOD = 1000000007;

int main() {
  int A, B; cin >> A >> B;
  string result;
  if ((A*B)%2==0) result = "Even";
  else result = "Odd";
  cout << result << endl;
  return 0;
}

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

//#define kk
#define int long long
#define FOR(i, n) for(int i=1; i<=n; i++)
#define ff first
#define ss second
#define ll int
#define inf 1000000000

const long long INF=1e18+5;
 
typedef pair<int, int> pi;

int wt[101];
int val[101];

void solve(){
	int n, w;
	cin>>n>>w;
	
	int v=0;
	for(int i=1; i<=n; i++){
		cin>>wt[i]>>val[i];
		v+=val[i];
	}
	
	vector<vector<int>> dp(n+1, vector<int> (v+1, INF));
	
	for(int i=0; i<=n; i++) dp[i][0]=0;
	
	int ans=0;
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=v; j++){
			if(val[i]<=j) dp[i][j]=min(wt[i]+dp[i-1][j-val[i]], dp[i-1][j]);
			else dp[i][j]=dp[i-1][j];
			
			if(dp[i][j]<=w) ans=max(ans, j);
		}
	}
	
	cout<<ans<<endl;
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	#ifdef kk
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
	
	int T=1;
	//cin>>T;
	
	while(T--){
		solve();
	}
}


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

void call(int n); 
int main(){

	int n;
	cin >> n;
	int a[n];
	
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	for (int i = 0; i < n; ++i)
	{	if(i==n-1){
		cout << a[n-1-i];
		}else{
		cout << a[n-1-i] << " ";
		}
	}
	cout << endl;


return 0;
}

Measured memory_bytes: 1160
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2439&lang=jp>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */
const ll MOD = 1e9+7;
ll solve(){
    ll res = 0;
    ll n; cin >> n;
    vector<char> c;
    for(int i = 0; i < n;i++){
        char tmp; cin >> tmp;
        if(tmp != '-') c.push_back(tmp);
    }
    ll sz = c.size();
    using VLL = vector<ll>;
    using VVLL = vector<VLL>;
    using VVVLL = vector<VVLL>;
    VVVLL dp(sz+1,VVLL(sz+1,VLL(sz+1,0)));
    dp[0][0][0] = 1;
    for(int i = 0; i < sz;i++){
        for(int j = 0; j <= i;j++){
            for(int k = 0; k <= i;k++){
                if(dp[i][j][k] == 0) continue;
                if(c[i] == 'U'){
                    (dp[i+1][j+1][k+1] += dp[i][j][k])%=MOD; // 割り当てを決めない
                    (dp[i+1][j][k] += dp[i][j][k]*k)%=MOD; // 今まで割り当てられていない人に割り当てる
                }else{
                    (dp[i+1][j][k] += dp[i][j][k]*j)%=MOD; // 今まで未割り当ての人を割り当てる
                    if(j > 0 && k > 0){ // i番目と今まで割り当てられていない人を同時に決める
                        (dp[i+1][j-1][k-1] += dp[i][j][k]*j*k)%=MOD;
                    }
                }
            }
        }
    }
    res = dp[sz][0][0];
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cout << solve() << endl;
    return 0;
}



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

#define N 1000

struct{int a[3];} d[N];

int main(){
    int i,j,L;
    int longest,small;
    scanf("%d",&j);
    for(i=0; i<j && i<N; i++)
        scanf("%d %d %d",&d[i].a[0],&d[i].a[1],&d[i].a[2]);
    L=i;
    for(i=0;i<L;i++){        
        longest=0; small=0;
        for(j=0;j<3;j++)
            if(longest<d[i].a[j])
                longest=d[i].a[j];
        for(j=0;j<3;j++)
            if(d[i].a[j]!=longest)
                small+=pow(d[i].a[j],2);
        if(small==pow(longest,2))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

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

int main(){
    int n,x,tmp=0,ans=1;
    cin >> n >> x;
    vector<int> l(n);
    for(int i=0;i<n;i++){
        cin >> l.at(i);
        tmp+=l.at(i);
        if(tmp<=x)ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3660
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<deque>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#include<regex>
#include<bitset>
#include<complex>
#include<chrono>
#include<random>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

ll gcd(ll n, ll m) {
	ll tmp;
	while (m!=0) {
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m) {
	return abs(n * m) / gcd(n, m);//gl=xy
}
 
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;
//ここから

void solve(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  cout<<max(a*b,c*d);
}

int main(){
	ios::sync_with_stdio(false);
  cin.tie(0);
	cout<<fixed<<setprecision(15);
  solve();
	return 0;
}


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

int main(){
    long long A, B, C, D; cin >> A >> B >> C >> D;
    A--;
    long long CD = C * D / __gcd(C,D);
    cout <<  B - A - (B/C + B/D - B/(CD) - (A/C + A/D - A/(CD))) << endl;
}


Measured memory_bytes: 256
AAs = [list(map(int, input().split())) for _ in range(3)]
N = int(input())
Bs = [int(input()) for _ in range(N)]
CCs = [
    [False, False, False],
    [False, False, False],
    [False, False, False],
]

for b in Bs:
    for x in range(3):
        for y in range(3):
            if AAs[x][y] == b:
                CCs[x][y] = True

def check():
    for cs in CCs:
        if all(cs): 
            return True
    for cs in list(map(list, zip(*CCs))):
        if all(cs): 
            return True
    if CCs[0][0] and CCs[1][1] and CCs[2][2]:
        return True
    if CCs[0][2] and CCs[1][1] and CCs[2][0]:
        return True

    return False

print("Yes" if check() else "No")

Measured memory_bytes: 3064
from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

N = int(stdin.readline().rstrip())
abc = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]

# i日目に(0, 1, 2):=(a, b, c)の行動を行った時の幸福度の最大値
dp = [[-INF] * 3 for _ in range(N+10)]

a, b, c = abc[0]
dp[0][0] = a
dp[0][1] = b
dp[0][2] = c

for i in range(N-1):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][j] =  max(dp[i+1][j], dp[i][k]+abc[i+1][j])

print(max(dp[N-1]))


Measured memory_bytes: 95192
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

using ll = long long;
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define tc() int t; cin>>t; while(t--)
#define print(n) cout<<n<<"\n"
#define inp(n) int n; cin>>n
#define all(cont) cont.begin(), cont.end()
#define foreach(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define mp make_pair
#define pb push_back
#define maxn 1000010
#define mod 1e9+7
#define ff  first
#define ss  second
#define fora(var, start, end) for(int var = start; var < end; var++)
int main()
{
    fast();
    ll h,k,sum=0;
    cin>>h>>k;
    vector<ll> v(h);
    fora(i,0,h){cin>>v[i]; }
    sort(all(v),greater<int>());
    if(k>=h)
    {
        print("0"); return 0;
    }
    fora(i,k,h)
    {
        sum+=v[i];
    }
    print(sum);
    return 0;
}

Measured memory_bytes: 1792
import math

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

tmpA = max(a, b)
tmpB = min(a, b)

while tmpB != 0:
    newB = tmpA % tmpB
    tmpA = tmpB
    tmpB = newB

tmp = tmpA
res = 1

for i in range(2, int(math.sqrt(tmp)) + 1):
    if tmp % i == 0:
        res += 1
        tmp //= i
    else:
        continue

    while tmp % i == 0:
        tmp = tmp//i


if tmp != 1:
    res += 1

print(res)


Measured memory_bytes: 3064
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <complex>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010


int main(){
  ll n,m;
  ll ans = 0;
  
  scanf("%lld%lld",&n,&m);

  if(n > m) swap(n,m);

  if(n == 1){
    if(m == 1){
      ans = 1;
    }else{
      ans = m-2;
    }
  } else {
    ans = (m-2) * (n-2);
  }

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



Measured memory_bytes: 256
#include<stdio.h>
#define MAXN 100000
int main ()
{  int n,k,s,i;
   scanf("%d %d %d",&n,&k,&s);
   for(i=1;i<=k;i++)
     {   if(i<=n-1) printf("%d ",s);
         else
         printf("%d",s);
     }
     if(s==1000000000)  s=s-2;
     for(i=k+1;i<=n;i++)
      {  if(i<=n-1) printf("%d ",s+1);
         else
         printf("%d",s+1);
     }
     return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;}
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define pb push_back
#define mod 1000000007
#define infi 1900000000
#define infl 1100000000000000000
#define cyes cout << "Yes" << endl
#define cno cout << "No" << endl
#define csp << " " <<
#define outset(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using ve = vector<T>;
template<typename T> using pq2 = priority_queue<T>;
template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>;
template <typename T> bool chmax(T &a, T b) {if(a < b) {a = b;return 1;}return 0;}
template <typename T> bool chmin(T &a, T b) {if(a > b) {a = b;return 1;}return 0;}




int main()
{
    int N;
    cin >> N;
    vi x(N);
    in(N,x);

    int ans = infi;
    reps(i,1,101){
        int a = 0;
        rep(j,N){
            a += (i-x[j])*(i-x[j]);
        }
        chmin(ans,a);
    }

    cout << ans << endl;
    
    
    
    

    return 0;
}


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

template<typename T>
T gcd(T a, T b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

int main() {
    int K; cin >> K;
    ll sum = 0;

    for (ll i = 1; i <= K; ++i) {
        for (ll j = 1; j <= K; ++j) {
            for (ll k = 1; k <= K; ++k) {
                ll g = gcd(i ,j);
                g = gcd(g, k);
                sum += g;
            }
        }
    }
    cout << sum << endl;
}


Measured memory_bytes: 3632
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#include <fstream>
#include <random>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <functional>
#include <random>
#include <time.h>
#include <chrono>
#include <sstream>
#include <iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define mod 1000000007
#define sort(s) sort(s.begin(), s.end());
#define reverse(s) reverse(s.begin(), s.end());
#define P pair<int,int>
#define mp make_pair
#define valid(x,y,h,w) (0<=x&&x<h&&0<=y&&y<w)
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
using namespace std;
int POW(int x, int y) { return int(pow(double(x), double(y))); }
double log(double a, double b) { return log(b) / log(a); }





int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> to(n), len(n), num(n);
	rep(i, m) {
		int a, b, c;
		cin >> a >> b >> c;
		--a; --b;
		to[a].push_back(b);
		len[a].push_back(c);
		to[b].push_back(a);
		len[b].push_back(c);
	}
	map<P,int> used;
	rep(i0, n) {
		vector<P> m(n,mp(INF,-1));
		rep(j, to[i0].size()) {
			m[0];
			m[to[i0][j]] = mp(0 + len[i0][j], i0);
		}
		int i = i0;
		while (1) {
			int minl = INF;
			int mint = -1;
			int minf = -1;
			rep(j, n) {
				if (minl > m[j].first && m[j].first != 0) {
					minl = m[j].first;
					minf = m[j].second;
					mint = j;
				}
			}
			if (mint == -1) {
				break;
			}
			used[mp(minf, mint)] = 1;
			used[mp(mint, minf)] = 1;
			rep(j, to[mint].size()) {
				auto newT = to[mint][j];
				if (m[newT].first > m[mint].first + len[mint][j]) {
					m[newT].first = m[mint].first + len[mint][j];
					m[newT].second = mint;
				}

			}
			m[mint].first = 0;
			i = mint;
		}
	}
	cout << m - used.size() / 2 << endl;
	return 0;

}



Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define sign(x) ((x==0)?1:-1)


int main(){
	int N,M;
	cin>>N>>M;
	vector<long long> A(N);
	vector<long long> B(N);
	vector<long long> C(N);

	for(int i=0;i<N;i++){
		cin>>A[i]>>B[i]>>C[i];
	}
	long long maxi = 0;
	
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++){
				vector<long long> V(N);
				for(int x=0;x<N;x++){
					V[x]=A[x]*sign(i)+B[x]*sign(j)+C[x]*sign(k);
				}
				sort(V.begin(),V.end(),greater<long long>());
				long long a = 0;
				for(int x=0;x<M;x++){
					a+=V[x];
				}
				maxi = max(a,maxi);
				
			}
		}
	}
	
	cout<<maxi<<endl;
	
	
	return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {

	public static void main(String[] args) {
		int mod = 1_000_000_007;
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		long[][] com = new long[2001][2001];
		for(int i = 0; i < 2001; i++)
			com[i][0] = 1;
		for(int i = 1; i < 2001; i++) {
			for(int j = 1; j <= i; j++) {
				com[i][j] = com[i-1][j-1] + com[i-1][j];
				com[i][j] %= mod;
			}
		}
		for(int i = 1; i <= K; i++) {
			long ans = com[N-K+1][i]*com[K-1][i-1];
			ans %= mod;
			System.out.println(ans);	
		}

	}

}


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

int n;
set<vector<char> > st;
string str;
vector<char> res;
bool f[30];

void print(vector<char> vc){
  for(int i=0;i<vc.size();i++) cout << vc[i];
  cout << endl;
}

void func(int pos){
  if(pos >= n){
    st.insert(res);
    
  } else {
    if(str[pos] + 1 <= 'z' && !f[str[pos]-'a']){
      res.push_back(str[pos] + 1);
      f[str[pos]-'a'] = true;
      func(pos+1);
      f[str[pos]-'a'] = false;
      res.pop_back();
    } 

    if(str[pos] == 'a' || f[str[pos]-1-'a']){
      res.push_back(str[pos]);
      func(pos+1);
      res.pop_back();
    }
  }
}

void solve(){
  n = str.size();
  st.clear();
  
  res.clear();
  fill(f,f+30,false);
  func(0);
  
  cout << st.size() << endl;
  if(st.size() <= 10){
    for(set<vector<char> >::iterator it = st.begin(); it != st.end(); it++){
      print(*it);
    }
  } else {
    set<vector<char> >::iterator it = st.begin();
    for(int i=0;i<5;i++,it++) print(*it);
    it = st.end();
    for(int i=0;i<5;i++) it--;
    for(int i=0;i<5;i++,it++) print(*it);
  }
}

int main(){
  while(cin >> str && str != "#") solve();
}

Measured memory_bytes: 2864
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

n = ni()
if n % 2 == 0:
    print((n // 2) / n)
else:
    print((n // 2 + 1) / n)


Measured memory_bytes: 38256
from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m,d=zip(*eval('(input(),[I]*w),'*h))
q=deque([(s-1,t-1,1)])
while q:
 y,x,c=q.popleft()
 if d[y][x]>c:
  for i in range(y-2,y+3):
   for j in range(x-2,x+3):d[y][x]=c;h>i>-1<j<w<d[i][j]!=m[i][j]>'#'!=(abs(y-i)+abs(x-j)<2!=q.appendleft((i,j,c))or q.append((i,j,c+1)))
print(d[f-1][g-1]%I-1)

Measured memory_bytes: 229044
from collections import defaultdict
MOD = 10**9+7
n = int(input())
dp = [1]
d = defaultdict(list)
cur = int(input())
d[cur].append(0)
for i in range(1,n):
  pre,cur = cur,int(input())
  c = dp[-1]
  if pre != cur and d[cur]:
    c += dp[d[cur][-1]]
  dp.append(c%MOD)
  d[cur].append(i)
print(dp[-1])

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

const int maxn = 2e5+5;
int n, m;
vector<int> adj[maxn];
bool vis[maxn];
int comp[maxn];

void dfs(int i, int pt) {
    comp[pt]++;
    vis[i] = true;
    for (int j: adj[i]) {
        if (!vis[j]) {
            dfs(j,pt);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int pt = 0;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(i,pt);
            ans = max(ans,comp[pt]);
            pt++;
        }
    }
    cout << ans << '\n';
}


Measured memory_bytes: 23964
#pragma GCC optimize("trapv")
#include<bits/stdc++.h>
#define int ll
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
const int maxn = 1<<20, mod = 119<<23|1;
const int B = 299977, C = 1139123;
int n, pw[maxn], pw2[maxn], ps = 0, ans = 0;
array<ll, 2> F[maxn];
string s;
map<array<ll, 2>, int> cnt;
void add(int &a, int b) {
	a = a+b>=mod?a+b-mod:a+b;
}
ll bp(ll a, ll p) {
	ll r = 1;
	while(p) {
		if(p&1) r = r*a%mod;
		a = a*a%mod, p>>=1;
	}
	return r;
} 
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> s;
	pw[0] = pw2[0] = 1;
	for(int i = 1; i < maxn; i++) pw[i] = pw[i-1]*1ll*B%mod;
	for(int i = 1; i < maxn; i++) pw2[i] = pw2[i-1]*1ll*C%mod;
	cnt[{0, 0}]++;
	array<ll, 2> cur = {0, 0};
	for(int i = 0; i < n; i++) {
		if(s[i] == '>') ps++;
		if(s[i] == '<') ps--;
		if(s[i] == '+') {
			add(cur[0], pw[(maxn/2) + ps]);
			add(cur[1], pw2[(maxn/2) + ps]);
		}
		if(s[i] == '-') {
			add(cur[0], mod-pw[(maxn/2) + ps]);
			add(cur[1], mod-pw2[(maxn/2) + ps]);
		}
		F[i+1] = cur;
		cnt[cur]++;
	}
	F[0] = {0, 0};
	ps = 0;
	array<ll, 2> ccur = {0, 0};
	for(int ps = 0, i = 0; i <= n; i++) {
		cnt[F[i]]--;
		ll X = (bp(B, mod-1+ps)*1ll*cur[0] + ccur[0])%mod;
		ll Y = (bp(C, mod-1+ps)*1ll*cur[1] + ccur[1])%mod;
		ans += cnt[{X, Y}];
		if(i == n) continue;
		if(s[i] == '>') ps++;
		if(s[i] == '<') ps--;
		if(s[i] == '+') {
			add(ccur[0], pw[(maxn/2) + ps]);
			add(ccur[1], pw2[(maxn/2) + ps]);
		}
		if(s[i] == '-') {
			add(ccur[0], mod-pw[(maxn/2) + ps]);
			add(ccur[1], mod-pw2[(maxn/2) + ps]);
		}
	}
	cout << ans << '\n';
}


Measured memory_bytes: 55052
#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;


int main(){
    string a,b,c; cin >> a;
    cin >> b;
    cin >> c;
    cout << a[0] << b[1] << c[2] << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
	
	ll t;
	cin>>t;
    ll f=0,z;
	while(t!=0)
    {
      z=t%10;
      t=t/10;
      if(z==7)
        f=1;
    }
      if(f==1)
        cout<<"Yes";
    else
      cout<<"No";
      return 0;
}

Measured memory_bytes: 3624
l = list(map(int,input().split()))
x = abs(l[0])
k = l[1]
d = l[2]
prev = 0

n = x//d

if k%2 == 0 and n%2 == 1:
  n += 1
elif k%2 == 1 and n%2 == 0:
  n += 1

if n>k:
  n = k
ans = abs(x-n*d)
print(ans)

Measured memory_bytes: 9196
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <numeric>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <memory>
#include <thread>
#include <tuple>

using namespace std;

int main() {
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);
  if (a == b && b == c) {
    printf("Yes\n");
  }
  else {
    printf("No\n");
  }
  return 0;
}


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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  int t_turn = 0;
  int a_turn = 0;
  if(b >= c) t_turn = 1;
  else {
    if(c % b == 0) t_turn = c / b;
    else t_turn = (c / b) + 1;
  }
  if(d >= a) a_turn = 1;
  else {
    if(a % d == 0) a_turn = a / d;
    else a_turn = (a / d) + 1;
  }
  
  bool flag = false;
  if(t_turn <= a_turn) flag = true;
  
  if(flag) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3596
#include <iostream> 
#include <iomanip> 
#include <vector> 
#include <algorithm> 
#include <numeric> 
#include <functional> 
#include <cmath> 
#include <queue> 
#include <stack> 

#define Ford(a,b) for (int i=(a);i<(b);i++) 
#define For(n) Ford(0,n) 
typedef long long ll; 

using namespace std;

int main(){
  int a[4],num;
  cin>>num;
  For(4) {
    a[i]=num%10;
    num/=10;
  }
  For(2){
  if((a[i]==a[i+1]) &&(a[i+i]==a[i+2])) 
  {cout << "Yes" << endl;return 0;}
  }
  cout << "No" << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdio>
#include <list>
#define ll long long
#define rep2(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(int i=a;i>=b;i--)
#define REP(e,v) for(auto e:v)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define edge(v,a,b) v[a].pb(b);v[b].pb(a);
#define vec vector<int>
#define vecll vector<ll>
#define vecstr vector<string>
#define vecch vector<char>
#define vecpii vector<pii>
#define bs binary_search
#define All(c) (c).begin(),(c).end()
using namespace std;
int in(){int x;scanf("%d",&x);return x;}
string stin(){string s;cin>>s;return s;}
char chin(){char c;cin>>c;return c;}
ll lin(){ll x;scanf("%lld",&x);return x;}
int main(){
    string s=stin();
    int a=-1,b=(int)s.length()+1;
    rep(i,s.length()){if(s.at(i)=='A'&a==-1)a=i;if(s.at(s.length()-1-i)=='Z'&b==s.length()+1)b=(int)s.length()-i;}
    cout<<b-a<<endl;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <stdlib.h>
#include <iostream>

using namespace std;

int main(){
  int A,B;
  cin >>A>>B;
  if (A>=13){
    cout <<B;
  }  
  else if (A>=6){
    cout <<B/2;
  }  
  else{
    cout <<0;
  }
}  

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
using namespace std;
#define MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec; typedef pair<int, int> pi;
int dd[] = { 0, 1, 0, -1, 0 };


int main()
{
	int X, A, B;
	scanf("%d%d%d", &X, &A, &B);
	if (A - B >= 0)
	{
		printf("delicious\n");
	}
	else if (X >= B - A)
	{
		printf("safe\n");
	}
	else
	{
		printf("dangerous\n");
	}
	

	return 0;
}


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

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define go(i,s,t) for(int i = s; i >= t; -- i)
const int MaxN = 100050;

long long ans = 0, A, B, x[MaxN];
int n;

int main()
{
	scanf("%d%lld%lld",&n,&A,&B);
	fo(i,1,n) scanf("%lld",&x[i]);
	fo(i,2,n)
	{
		if((x[i]-x[i-1])*A>B) ans += B;
		else ans += (x[i]-x[i-1])*A;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 1024
#![allow(dead_code,unused_variables)]
use proconio::{fastout, input};
use proconio::marker::Usize1;
use std::cmp::max;
use std::mem::swap;

fn main() {
    input! {
        n: usize,
        m: usize,
        p : [(Usize1,Usize1);m],
    } 
    let mut uf = UnionFind::new(n);

    for e in p{
        // println!("{:?}",e);
        
        uf.unite(e.0,e.1);
        // println!("{}",uf.get_size(0));
        // println!("------");
    }

    let mut ans = 0;
    for i in 0..n{
        ans = max(uf.get_size(i),ans);
        // println!("{}",uf.get_size(i));
    }

    println!("{}",ans);

}

struct UnionFind{
    par : Vec<usize>,
    size : Vec<usize>,
}

impl UnionFind{
    pub fn new(n: usize) -> Self{
        let par : Vec<usize>= (0..n).collect();
        UnionFind{
            par,
            size : vec![1;n],
        }
    }

    pub fn root(&mut self,x : usize) -> usize{
        if self.par[x] == x{
            return x;
        }

        self.par[x] = self.root(self.par[x]);
        self.par[x]
    }

    pub fn unite(&mut self, x: usize, y: usize){
        let mut rx = self.root(x);
        let mut ry = self.root(y);

        if rx == ry{
            return;
        }

        if self.size[rx] < self.size[ry]{
            swap(&mut rx,&mut ry);
        }
        self.size[rx] += self.size[ry];
        self.par[ry] = rx;
    }

    pub fn same(&mut self, x: usize, y: usize) -> bool{
        self.root(x) == self.root(y)
    }

    pub fn get_size(&mut self, x: usize) -> usize{
        let tmp = self.root(x);
        self.size[tmp]
    }
}


Measured memory_bytes: 10804
n,m=gets.split.map(&:to_i)
a=Array.new(m){[false]*n}
n.times do |j|
  _,*l=gets.split.map(&:to_i)
  l.each do |i|
    a[i-1][j]=true
  end
end
ans = m
a.each do |aa|
  aa.each do |bool|
    unless bool
      ans-=1
      break
    end
  end
end
p ans


Measured memory_bytes: 14264
#include <bits/stdc++.h>
using namespace std;
int main(){
	long long n,hasil,sisa;
	cin>>n;
	sisa=n%11;
	hasil=n/11*2;
	if (sisa>6) hasil+=2;
	else if (sisa>0 and sisa<=6) ++hasil;
	cout<<hasil<<endl;
}

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

using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;

int main(void) {
    int k;
    cin >> k;
    string s;
    cin >> s;
    if(s.size() <= k) {
        cout << s << endl;
    }else {
        rep(i, k) {
            cout << s[i];
        }
        cout << "..." << endl;
    }
    return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <time.h>
#define int long long
#define endl '\n'
#define INF 1000000000000000000
#define EPS 1e-10
#define PI 3.141592653589793238
#define all(a) a.begin(),a.end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define pb push_back
#define double long double
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
typedef complex<double> com;
template<class T, class S> bool chmax(T &a, const S &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class S> bool chmin(T &a, const S &b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }


signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	//modcalc();

	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	vector<int> cnt(n);
	vector<int> ans;
	for (int i = n; i >= 1; i--) {
		int s = 0;
		for (int j = i; j <= n; j += i) {
			if (cnt[j - 1]) s ^= 1;
		}
		if (s != a[i - 1]) {
			ans.pb(i);
			cnt[i - 1] = 1;
		}
	}
	cout << ans.size() << endl;
	for (int i : ans) cout << i << ' ';
	if (ans.size() > 0) cout << endl;
}

Measured memory_bytes: 5108
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
using ll = long long;
using graph = std::vector<std::vector<ll>>;

using namespace std;

ll memo[10005][1005];//memo[HP][magicIndex]
vector<pair<ll,ll>> M(1005);//M[cost][damage]
int init(){
    for(int yi = 0; yi < 1005; yi++){
        for(int xi = 0; xi < 10005; xi++){
            if(xi == 0){
                memo[xi][yi] = 0;
                continue;
            }
            memo[xi][yi] = 1ll << 50;
        }
    }
}

int solve(int HP, int magicIndex){
    if(memo[HP][0] != 1ll << 50){
        return memo[HP][0];
    }
    ll minCost = 1ll << 50;
    for(int i = 0; i < magicIndex; i++){
        //cout << HP - M[i].second << "   " << M[i].first;
        ll tmpCost = solve(max(0ll,HP - M[i].second), magicIndex) + M[i].first;
        minCost = min(minCost,tmpCost);
    }
    memo[HP][0] = minCost;
    return minCost;

}

int main() {
    init();
    ll H,N;
    cin >> H >> N;
    for(int i = 0; i < N; i++){
        ll a,b;
        cin >> a >> b;
        M[i] = make_pair(b,a);
    }

    ll minCost = 1ll << 50;
    minCost = solve(H,N);
    /*
    for(int yi = 0; yi < H; yi++){
        for(int xi = 0; xi < N; xi++){
            cout << memo[yi][xi] << ",";
        }
        cout << endl;
    }
     */
    cout << minCost << endl;

}

Measured memory_bytes: 79488
function main(input) {
    var args = input.split('\n');
  	var a = args[1].split(' ');
  	var max = 0;
    var res = 0;
  	for(var i = 0; i < args[1].length; i++){
        var m = parseInt(a[i],10);
    	if(m >= max){
        	res++;
          	max = m;
        }
    }
  	console.log(res);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 9420
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const long long INF = 1e15;

int main(){

    ll n,k;
    cin >> n >> k;
    vector<vector<ll>> cost(n);
    vector<ll> p(n),c(n), sum(n,0);
    for(ll i = 0; i < n; i++) cin >> p[i], p[i]--;
    for(ll i = 0; i < n; i++) cin >> c[i];
    
    for(ll i = 0; i < n; i++){
        ll now = i;
        while(true){
            now = p[now];
            cost[i].push_back(c[now]);
            sum[i] += c[now];
            if(now == i) break;
        }
    }

    auto calc = [&](ll i,ll n,bool z){
        ll mx = cost[i][0];
        ll tmp = 0;
        if(z) mx = max(0ll,mx);
        for(ll j = 0; j < n; j++){
            tmp += cost[i][j%cost[i].size()];
            mx = max(mx,tmp);
        }  
        return mx;
    };

    ll ans = -mod*mod;

    for(ll i = 0; i < n; i++){
        ll cs = cost[i].size();
        ll fir = calc(i,min(cs,k),false);
        ans = max(ans,fir);
        if(sum[i] <= 0) continue;
        ll can;
        if(cs <= k && k <= 2*cs){
            can = calc(i,k,false);
        } else {
            can = sum[i]*((k/cs)-1);
            int m = k%cs+cs;
            can += calc(i,m,true);
        }
        ans = max(can,ans);
    }

    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 218948
#include <stdio.h>
#include <iostream>
using namespace std;
int main(){
    string a[16],temp;
    a[0]="AKIHABARA";
    a[1]="AKIHABAR";
    a[2]="AKIHABR";
    a[3]="AKIHBARA";
    a[4]="AKIHBAR";
    a[5]="AKIHABRA";
    a[6]="AKIHBRA";
    a[7]="AKIHBR";
    a[8]="KIHABARA";
    a[9]="KIHABAR";
    a[10]="KIHABR";
    a[11]="KIHBARA";
    a[12]="KIHBAR";
    a[13]="KIHABRA";
    a[14]="KIHBRA";
    a[15]="KIHBR";
    cin>>temp;
    for(int i=0;i<16;i++)if(temp==a[i]){
        cout<<"YES"<<endl;
        return 0;
    }
    cout<<"NO"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <queue>
#include <stdio.h>
using namespace std;

struct data{
	int v,c;
};

bool cmp(data x,data y){
	if(x.c < y.c)	return true;
	else			return false;
}

main(){
	
	int n,m,k;
	long long ans;
	data a[100010];
	priority_queue<int> pq;
	ans = 0;
	k = 1;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i].c,&a[i].v);
	sort(a+1,a+n+1,cmp);
	a[n+1].c = -1;
	for(int i=1;i<=m;i++){
		for(;a[k].c == i && k <= n;k++)
			pq.push(a[k].v);	
		
		if(!pq.empty()){
			ans += pq.top();
			pq.pop();
		}
	}
	cout<<ans<<'\n';
}

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

using namespace std;
using ll = long long;


int main()
{
    int n; cin >> n;
    vector<int> unit(13);
    unit[0]++;
    for(int i = 0; i < n; i++) {
        int a; cin >> a; unit[a]++;
        if(unit[a] == 3) {
            cout << 0 << endl;
            return 0;
        }
    }
    int ans = 0;

    for(int bit = 0; bit < (1 << 13); bit++) {
        vector<int> tim;
        for(int i = 0; i < 13; i++) {
            if((bit & (1 << i)) && unit[i] == 1) {
                tim.push_back(24 - i);
            } else {
                if(!unit[i])continue;
                tim.push_back(i);
                if(unit[i] == 1)continue;
                tim.push_back(24 - i);
            }
        }

        sort(tim.begin(), tim.end());
        tim.resize(unique(tim.begin(), tim.end()) - tim.begin()); 
        int m = tim.size();
        int nin = 13;

        for(int i = 0; i < m; i++) {
            for(int j = i + 1; j < m; j++) {

                int d = abs(tim[i] - tim[j]);
                if(d == 24)d = 0;
                nin = min(nin, min(d, 24 - d));

            }
        }
        ans = max(nin, ans);
    }
    cout << ans << endl;
}

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

int main() {
 int n; cin >> n;
  if(n <=599)
   cout << 8 << endl;
  else if(n <=799)
   cout << 7 << endl;
  else if(n <=999)
   cout << 6 << endl;
  else if(n <=1199)
   cout << 5 << endl;
  else if(n <=1399)
   cout << 4 << endl;
  else if(n <=1599)
   cout << 3 << endl;
  else if(n <=1799)
   cout << 2 << endl;
  else
   cout << 1 << endl;
}


Measured memory_bytes: 3668
def main():
    a = [[int(x) for x in input().split()] for _ in range(3)]
    n = int(input())

    t = [[0] * 3 for _ in range(3)]

    for _ in range(n):
        b = int(input())
        for r in range(3):
            for c in range(3):
                if a[r][c] == b:
                    t[r][c] = 1

    for r in range(3):
        if t[r][0] == t[r][1] == t[r][2] == 1:
            print('Yes')
            return

    for c in range(3):
        if t[0][c] == t[1][c] == t[2][c] == 1:
            print('Yes')
            return

    if t[0][0] == t[1][1] == t[2][2] == 1:
        print('Yes')
        return

    if t[0][2] == t[1][1] == t[2][0] == 1:
        print('Yes')
        return

    print('No')


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Measured memory_bytes: 3064
S = input()
cnt = 0
cntmax = 0
for i in range(len(S)):
    if S[i] == "A" or S[i] == "T" or S[i] == "G" or S[i] == "C":
        cnt+=1
        if cnt>cntmax:
            cntmax = cnt
    else:
        cnt = 0

print(cntmax)

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

int main()
{
  int64_t n, ans = 0, i = 357, ma = 777777777;
  string s;
  cin >> n;
  ma = min(n, ma);
  map<char, int> sft;

  while (i <= ma)
  {
    map<char, int> sft;
    s = to_string(i);

    bool flag = 1;
    int cnt = (int)s.size();

    for (char c : s)
    {
      if (c != '7' and c != '5' and c != '3')
      {
        flag = 0;
        i += (pow(10, cnt - 1));

        break;
      }
      else
      {
        ++sft[c];
      }
      --cnt;
    }
    if (flag)
    {
      if (sft.count('7') and sft.count('5') and sft.count('3'))
      {
        ++ans;
      }
      ++i;
    }
  }

  cout << ans << "\n";
}

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

#define ll long long
#define dd double
#define scl(n)    scanf("%lld",&n)
#define scd(n)    scanf("%lf",&n)
#define ptl(n)    printf("%lld",n)
#define ptd(n)    printf("%lf",n)
#define nline     printf("\n")
#define vld       vector<ll>
#define vbd       vector<bool>
#define eb        emplace_back
#define FOR(i,n)  for(ll i=0;i<n;i++)
#define FOR1(i,n) for(ll i=1;i<=n;i++)
#define pi        2*acos(0.0)

using namespace std;

int main()
{
    ll l,r,d,mul,cnt=0;
    scl(l);
    scl(r);
    scl(d);
    mul=d;
    for(ll i=1;mul<=r;i++)
    {
        if(mul>=l&&mul<=r)
            cnt++;
        mul+=d;
    }
    ptl(cnt);
    return 0;
}


Measured memory_bytes: 3812
H,W = map(int,input().split())
S = [input() for i in range(H)]

from collections import deque
dxy = [(0,1),(1,0),(0,-1),(-1,0)]
dist = [[0]*W for i in range(H)]
visited = [[0]*W for i in range(H)]
visited[0][0] = 1
q = deque([(0,0)])
while q:
    x,y = q.popleft()
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if visited[ny][nx]: continue
        if S[ny][nx] == '#': continue
        visited[ny][nx] = 1
        dist[ny][nx] = dist[y][x] + 1
        q.append((nx,ny))

dots = sum(row.count('.') for row in S)
print(dots - dist[-1][-1] - 1 if dist[-1][-1] else -1)

Measured memory_bytes: 3380
#include<stdio.h>
int A, B, C, D, X, Y;
int main(){
  scanf("%d%d%d%d", &A, &B, &C, &D);
  X = A<C?C:A;
  Y = B>D?D:B;
  if(X>Y){
    printf("0\n");
  }else{
    printf("%d\n", Y-X);
  }
}


Measured memory_bytes: 128