akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//const ull mod = 1e9 + 7;
const ll mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
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 (a>b) { a=b; return 1; } return 0; }

// conversion number to bit
string num2bit(ll num, ll len){
  string bit = "";
  REP(i, len){
    bit += char('0'+(num>>i & 1));
  }
  return bit;
}

using Graph = vector<vector<ll>>;
pll dfs(ll now, ll par, Graph &G){
	pll res = {0, now};
	for(auto next: G[now]){
		if(next == par) continue;
		auto cost = dfs(next, now, G);
		cost.first++;
		res = max(res, cost);
	}
	return res;
}

ll tree_diameter(Graph &G){
	auto p = dfs(0, -1, G);
	auto q = dfs(p.second, -1, G);
	// (p.second, q.second) is the diameter
	return q.first;
}

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

    ll N;
    cin >> N;

    Graph G(N);
    REP(i, N-1){
    	ll a, b;
    	cin >> a >> b;
    	a--, b--;
    	G[a].push_back(b);
    	G[b].push_back(a);
    }

    ll d = tree_diameter(G);

    if(d%3==1){
    	cout << "Second" << endl;
    }else{
    	cout << "First" << endl;
    }
    return 0;
}

Measured memory_bytes: 26880
#include <cstring>
#include <map>
#include <unordered_map>
#include <string>
#include <list>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <iostream>
#include <set>
#include <unordered_set>
using namespace std;

#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int, int> pii;

int gi() {
    int a;
    scanf("%d", &a);
    return a;
}

ll gli() {
    ll a;
    scanf("%lld", &a);
    return a;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n = gi();
    int a = gi();
    int b = gi();

    n *= a;
    a = MIN(n, b);
    printf("%d\n", a);

    return 0;
}


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

#define INF INT_MAX
#define UINF UINT_MAX
#define MOD 998244353
#define REP(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()

typedef long long ll;
typedef std::pair<int,int> pii;

using namespace std;

ll myPow(ll x, ll n, ll m){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % m, n / 2, m);
  else
    return x * myPow(x, n - 1, m) % m;
}

int main() {
    int n;
    cin >> n;
    vector<ll> v(n,0); 

    int max_num = 0;
    bool f = true;
    REP(i,n){
        int a;
        cin >> a;
        v[a]++;
        if(i == 0 && a != 0)f = false;
        max_num = max_num < a ? a : max_num;
    }

    if(!f){
        cout << 0 << endl;
        return 0;
    }

    if(n == 1){
        if(v[0] == 1)cout << 1 << endl;
        else cout << 0 << endl;
        return 0;
    }

    REP(i,n-1){
        if((i == 0 && v[i] != 1) || (v[i] == 0 && v[i+1] != 0)){
            cout << 0 << endl;
            return 0;
        }
    }

    ll ans = 1;
    for(int i = 1;i < max_num;i++){
        ans = (ans * myPow(v[i],v[i+1],MOD)) % MOD;
    }

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

Measured memory_bytes: 1024
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>

using namespace std;

map<pair<int, int>, int >mp;

void solve(int x)
{
    vector<int> a;
    a.clear();
    while(x) {
        a.push_back(x % 10);
        x /=10;
    }
    int n = a.size();
    mp[make_pair(a[0], a[n - 1])]++;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        solve(i);
    }
    int ans = 0;
    for(int i = 1; i <= 9; ++i) {
        for(int j = 1; j <= 9; ++j) {
//            printf("%d %d\n", mp[make_pair(i, j)], mp[make_pair(j, i)]);
            ans += mp[make_pair(i, j)] * mp[make_pair(j, i)];
        }
    }
    printf("%d\n", ans);
    return 0;
}



Measured memory_bytes: 256
N, M = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(M)]

groups = [[] for _ in range(N + 1)]
for p, y in PY:
	groups[p] += [y]

for i, g in enumerate(groups):
	g.sort()
	cities = {}
	for j, t in enumerate(g):
		cities[t] = j + 1
	groups[i] = cities

for p, y in PY:
	print("{:06d}{:06d}".format(p, groups[p][y]))


Measured memory_bytes: 70812
n = gets.to_i
a = [0] + gets.split.map(&:to_i)

(n/2).downto(1) do |i|
  s = 0
  i.step(n,i).each{|j| s += a[j] }
  a[i] = s % 2
end

ans = (1..n).select{ |i| a[i] == 1 }
puts ans.size, ans * " "

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

int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a % b); }

#define CIN(T, x) T x; cin >> x;
#define CINS(T, x, N) vector<T> x(N); for(int i = 0; i < (N); i++) { cin >> x[i]; }
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << " "; } cout << "\n";
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << "\n";

ll N, M;
int N_MAX = 1e5+5;
//int N_MAX = 30;
vector<int> parent(N_MAX);
vector<ll> treeSize(N_MAX, 1);

int root( int x ) {
    if ( x == parent[x] ) return x;
    parent[x] = root(parent[x]);
    return parent[x];
}

void unite(int x, int y) {
    int rx = root(x);
    int ry = root(y);
    if (rx == ry)  return;

    if (treeSize[rx] >= treeSize[ry]) {
        parent[ry] = rx;
        treeSize[rx] += treeSize[ry];
        treeSize[ry] = 0;
    } else {
        parent[rx] = ry;
        treeSize[ry] += treeSize[rx];
        treeSize[rx] = 0;
    }
}

bool same(int x, int y) {
    return root(x) == root(y);
}


int main() {

    cin >> N >> M;
    vector<int> A(M);
    vector<int> B(M);

    for (int i = 0; i < M; i++) {
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
    }

    vector<ll> ans(M);
    ans[M - 1] = N * (N - 1) / 2;

    for (int i = 0; i < N; i++) {
        parent[i] = i;
    }

    for (int i = M - 1; i > 0; i--) {

        if ( same(A[i], B[i]) ) {
            ans[i - 1] = ans[i];
        } else {
            ans[i - 1] = ans[i] - treeSize[parent[A[i]]] * treeSize[parent[B[i]]];
            unite(A[i], B[i]);
        }
    }

    for (int i = 0; i < M; i++) {
        cout << ans[i] << "\n";
    }

    return 0;
}

Measured memory_bytes: 4096
#include <cstdio>
using namespace std;
int n;
int main(){
    scanf("%d",&n);
    int price=n/1.08;
    for (int y=0;y<2;y++){
        //printf("%d %d\n",price,(int)(price*1.08+0.01));
        if ((int)(price*1.08+0.01)==n){
            printf("%d\n",price);
            return 0;
        }
        price++;
    }
    printf(":(");
}

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

int main(){
  int n, W;
  cin >> n >> W;
  vector<int> w(n+1), v(n+1);
  for(int i=1; i<= n;i++){
    cin >> w[i] >> v[i];
 }
 ll dp[n+1][W+1];
 for(int i =0; i<=n; i++){
     for(int j =0; j<=W; j++){ 
        dp[i][j] = 0;
   }
}
 for(int i= 1; i<=n;i++){
   for(int j =0; j<=W; j++){
    if(j-w[i]>=0) dp[i][j] = max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]);
   else  dp[i][j] = dp[i-1][j];
   }
}
cout << dp[n][W] << endl;
return 0;
}

Measured memory_bytes: 79104
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define RFOR(i, m, n) for (int i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define print(ele) cout << ele << endl
#define print10(ele) cout << fixed << setprecision(10) << ele << endl

using namespace std;
typedef long long ll;
typedef vector<int> ivec;
typedef vector<string> svec;
typedef vector<ll> lvec;

const int mod = 1e9 + 7;
const ll INF = 1000000000000000000LL;

int main() {
  int n;
  cin >> n;
  ivec p(n);
  REP(i, n) cin >> p[i];
  int ans = 0;

  REP(i, n) {
    if (p[i] == i + 1) {
      ans++;
      i++;
    }
  }

  print(ans);
  return 0;
}

Measured memory_bytes: 640
N,A,B = map(int,input().split())
if not (A+B-1 <= N <= A*B):
    print(-1)
    exit()
if B == 1:
    print(*list(range(1,A+1)))
    exit()

n = (N-A)//(B-1)
m = (N-A)%(B-1)

stack = [1,A+1]
lds_cnt = 1
while stack[-1] <= N:
    l = n if lds_cnt > m else n+1
    stack.append(stack[-1] + l)
    lds_cnt += 1

ans = []
while len(stack) > 1:
    ans += list(range(stack[-2], stack[-1]))
    stack.pop()
print(*ans)

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

using namespace std;

int main()
{
    //system("chcp 65001");

    int A1, A2, A3;
    cin >> A1 >> A2 >> A3;
    int ans = max({A1, A2, A3}) - min({A1, A2, A3});
    cout << ans;

    return 0;
}

Measured memory_bytes: 256
object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)

    val N = sc.nextInt()
    val d = Array.fill(N)(sc.nextInt())

    val res = for {
      i <- (0 until N-1)
      j <- (i+1 until N)
    } yield d(i) * d(j)
    println(res.sum)
  }

}

Measured memory_bytes: 27320
//
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define PI 3.14159265
#define EPS 1e-9
#define Pi acos(-1.0)
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
#define forr(i,a,b) for(int i=(a); i<(b); i++)
#define clean(arr,val) memset(arr,val,sizeof(arr))
#define forn(i,n) forr(i,0,n)
#define PB push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vpll;

/*CODE START HERE*/

string s;
int a, z;

int main(){
    ios::sync_with_stdio(0);
    cin >> s;
    a = z = 0;
    forn(i,(int)s.size()){
        if(s[i] == 'A'){
            a = i;
            break;
        }
    }

    for(int i = (int)s.size()-1; i >= 0; i--){
        if(s[i] == 'Z'){
            z = i;
            break;
        }
    }

    cout << z-a+1 << "\n";
    return 0;
}

Measured memory_bytes: 3788
#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;
#define rep(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define per(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, sum) memset(a, sum, sizeof(a))
#define lowbit(x) (x & -x)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define enter cout << endl
#define siz(x) ((int)x.size())
typedef long long ll ;
typedef unsigned long long ull ;
typedef vector <int> vi ;
typedef pair <int, int> pii ;
typedef pair <ll, ll> pll ;
typedef map <int, int> mii ;
typedef map <string, int> msi ;
const int N = 100010 ;
const int INF = 0x3f3f3f3f ;
const int iinf = 1 << 30 ;
const ll linf = 2e18 ;
const int MOD = 1000000007 ;
void print(int x) { cout << x << endl ; exit(0) ; }
void PRINT(string x) { cout << x << endl ; exit(0) ; }
void douout(double x){ printf("%lf\n", x + 0.0000000001) ; }

int n, h, w, ans ;
int a[N], b[N] ;

int main() {
	scanf("%d%d%d", &n, &h, &w) ;
	for (int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]) ;
	for (int i = 1; i <= n; i++)
	if (a[i] >= h && b[i] >= w) ans++ ;
	printf("%d\n", ans) ;
}

/*
写代码时请注意：
	1.ll？数组大小，边界？数据范围？
	2.精度？
	3.特判？
	4.至少做一些
思考提醒：
	1.最大值最小->二分？
	2.可以贪心么？不行dp可以么
	3.可以优化么
	4.维护区间用什么数据结构？
	5.统计方案是用dp？模了么？
*/


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<set>
#include<queue>
#include<map>
using namespace std;
int n;
string str;
int check(int a)
{
	map<string, int> m;
	for (int i = 1; i <=n + 1 - a; i++)
	{
		string s = str.substr(i - 1, a);
		if (m[s])
		{
			if (i - m[s] >= a) return true;
		}
		else
			m[s] = i;
	}
	return false;
}

int main()
{
	cin >> n >> str;
	int l = 0,r = n / 2;
	while (l <= r)
	{
		int mid = l + r >> 1;
		if (check(mid)) l = mid+1;
		else  r = mid-1;
	}
	cout << r << endl;

}

Measured memory_bytes: 6668
n, m = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(m)]
ls.sort()
res = 1
rmin = float('inf')
for l, r in ls:
    if l >= rmin:
        res += 1
        rmin = r
    else:
        rmin = min(rmin, r)

print(res)

Measured memory_bytes: 27872
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int N, T;
    while(cin >> N >> T){
        vector<pair<long long, long long>> vp;
        vector<int> z;
        for(int i=0;i<N;i++){
            int a, b; cin >> a >> b;
            if(a == 0){
                z.push_back(b);
            } else {
                vp.emplace_back(a, b);
            }
        }
        sort(vp.begin(), vp.end(), [](auto a, auto b){ return b.first*(a.second+1) < a.first*(b.second+1); });
        sort(z.begin(), z.end());
        vector<long long> dp(50, T+1);
        dp[0] = 0;
        for(auto& p : vp){
            for(int i=dp.size()-2;i>=0;i--){
                if(dp[i] > T) continue;
                dp[i+1] = min(dp[i+1], (p.first+1) * (dp[i]+1) + p.second);
            }
        }
        int res = 0;
        for(int i=0;i<dp.size();i++){
            if(dp[i] > T) continue;
            long long t = dp[i];
            int cur = i;
            for(auto& v : z){
                if(t + v + 1 > T) break;
                t += v + 1;
                ++cur;
            }
            res = max(res, cur);
        }
        cout << res << endl;
    }
}

Measured memory_bytes: 6256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7; bool fp,fl[N];
int n,p,w[N],len[N],val[N]; vector<int>v[N];
inline int read(){
	int num=0; char g=getchar(); while(g<48||57<g) g=getchar();
	while(47<g&&g<58) num=(num<<1)+(num<<3)+g-48,g=getchar(); return num;
}
inline void find(int u){
	long long res=0; int cnt=0,maxn=0; fl[u]=1;
	for(int i=0;i<len[u];i++){
		int x=v[u][i]; if(fl[x]) continue; find(x),cnt++,res+=val[x],maxn=max(maxn,val[x]);
	}
	if(!cnt) val[u]=w[u];
	else{
		val[u]=w[u]*2-res; long long c=w[u]-val[u]; if(val[u]<0||w[u]>res) fp=1; if(res-maxn<c) fp=1;
	}
}
int main(){
	n=read(); int u,t;
	for(int i=1;i<=n;i++) w[i]=read(); if(n==2) {if(w[1]==w[2]) puts("YES"); else puts("NO"); return 0;}
	for(int i=1;i<n;i++) u=read(),t=read(),v[u].push_back(t),v[t].push_back(u),len[u]++,len[t]++;
	for(int i=1;i<n;i++) if(len[i]>1) p=i; find(p); if(val[p]) fp=1;
	if(fp) puts("NO"); else puts("YES");
	return 0;
}

Measured memory_bytes: 10880
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
typedef long long ll;
const int mmax=1e5+10;
map<ll,ll> s;
ll book[mmax],num[mmax];
int main()
{
	ll n,k;
	while(cin>>n>>k)
	{
		memset(book,0,sizeof(book));
		memset(num,0,sizeof(num));
		s.clear();
		for(int i=1;i<=n;i++)
		{
			ll a,b;
			cin>>a>>b;
			s[a]+=b;
			num[i]=a;
		}
		ll sum=0;
		sort(num+1,num+n+1);
		for(int i=1;i<=n;i++)
		{
			if(num[i]!=num[i-1])
				book[i]=num[i];
		}
		sort(book+1,book+n+1);
		for(int i=1;i<=n;i++)
		{

			if(book[i]==0)
				continue;
			else
			{
				sum+=s[book[i]];
				if(sum>k||sum==k)
				{
					cout<<book[i]<<endl;
					break;
				}
			}	
		}
	}
	return 0;
 } 


Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
int main(){
  long N,K,C;cin>>N>>K>>C;
  string S;cin>>S;
  vector<long>L(K,0),R(K,N-1);//i+1個目があり得る左端と右端
  
  long t=0;
  for(long i=0;i<N;i++){
    if(S[i]=='o'){
      L[t]=i;t++;
      i+=C;
    }
    if(t>=K)break;
  }
  t=K-1;
  for(long i=N-1;i>=0;i--){
    if(S[i]=='o'){
      R[t]=i;t--;
      i-=C;
    }
    if(t<0)break;
  }
  for(long i=0;i<K;i++)if(R[i]==L[i])cout<<(R[i]+1L)<<endl;
  
}

Measured memory_bytes: 4996
def main():
  N,X,Y=map(int,input().split())

  C=[0]*N
  for i in range(1,N):
    for j in range(i+1,N+1):
      C[min(j-i,abs(X-i)+1+abs(j-Y))]+=1
  for i in range(1,N):
    print(C[i])

main()


Measured memory_bytes: 3444
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		long ini = 0;
		for(int i=0;i<N-1;i++){
			var x = A[i] < A[i+1] ? A[i+1] - A[i] : M - (A[i]-A[i+1]);
			var y = 1 + (0 <= A[i+1] ? A[i+1] - 0 : M - (0 - A[i+1]));
//Console.WriteLine("{0} {1}",x,y);
			ini += Math.Min(y,x);
		}
		
		var imos = new int[M+2];
		for(int i=0;i<N-1;i++){
			int ma = A[i] <= A[i+1] ? A[i+1] - A[i] : M - (A[i]-A[i+1]);
			
			imos[A[i+1]] -= (-1);
			if(A[i+1] - (ma - 1) >= 0){
				imos[A[i+1]-(ma - 1)] += -1;
			} else {
				imos[0] += -1;
				
				imos[M] -= -1;
				imos[M - (ma-1 - A[i+1])] += -1;
			}
			
			imos[A[i+1]] += (ma - 1);
			imos[A[i+1]+1] -= (ma - 1);
		}
		
		long[] sum = new long[M+2];
		for(int i=0;i<M;i++){
			sum[i] += imos[i];
			if(i>0) sum[i] += sum[i-1];
		}
		
		long ans = ini;
		long cur = ini;
		for(int i=0;i<M-1;i++){
			cur += sum[i];
			ans = Math.Min(ans,cur);
		}
		Console.WriteLine(ans);
		
	}
	int N,M;
	int[] A;
	public Sol(){
		var d = ria();
		N = d[0]; M = d[1];
		A = ria();
		for(int i=0;i<N;i++) A[i]--;
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 18144
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>
#include<cstdlib>
#include<ctime>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;

constexpr int num = 26;
int D;
vector<int> c(num);

vector<vector<int>> s; 

int point(vector<int> &t){
	int res = 0;
	
	vector<int> last(num);
	
	for(int i = 0; i < D; i++){
		res += s[i][t[i]];
		
		for(int j = 0; j < num; j++){
			last[j]++;
		}
		
		last[t[i]] = 0;
		
		for(int j = 0; j < num; j++){
			res -= c[j] * last[j];
		}
	}
	
	return res + 1'000'000;
}
signed main(){
	cout<<fixed<<setprecision(10);
	
	vector<int> t;
	vector<int> last(num);
	// srand(time(NULL));
	
	cin>>D;
	
	// D = 365;
	
	s.resize(D, vector<int>(num));
	t.resize(D, 0);
	
	for(int i = 0; i < num; i++){
		cin>>c[i];
		// c[i] = rand()%100;
	}
	
	for(int i = 0; i < D; i++){
		for(int j = 0; j < num; j++){
			cin>>s[i][j];
			// s[i][j] = rand()%20000;
			
			if(s[i][t[i]] + last[t[i]] * c[t[i]] < s[i][j] + last[j] * c[j]) {
				t[i] = j;
			}
		}
		
		for(int j = 0; j < num; j++){
			if(j == t[i]) {
				last[j] = 0;
			} else {
				last[j]++;
			}
		}
	}
	
	// srand(time(NULL));
	
	// cout<<point(t)<<endl;
	
	int p = point(t);
	
	for(int i = 0; i < 100; i++){
		int d = rand()%D, x = rand()%num, np;
		int tx;
		
		tx = t[d];
		
		t[d] = x;
		
		np = point(t);
		
		if(p < np) {
			np = p;
		} else {
			t[d] = tx;
		}
		
	}
	// cout<<point(t)<<endl;
	
	for(int i = 0; i < D; i++){
		cout<<t[i]+1<<endl;
	}
	
	
	return 0;
}

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


//ユーグリッドの互除法による最大公約数を求めるメソッド
ll gcd(ll a, ll b) {
  ll smaller = min(a, b);
  ll bigger = max(a, b);
  ll surplus = bigger % smaller;
  if (surplus == 0) return smaller;
  surplus = gcd(smaller, surplus);
  return surplus;
}

//最小公倍数を求めるメソッド
ll lcm(ll a, ll b) {
  return a * b / gcd(a, b);
}


int main() {
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  ll lc = lcm(c, d);
  ll num1 = a - 1;
  ll num1_c = num1 - ((num1 / c) + (num1 / d) - (num1 / lc));
  ll all = b - ((b / c) + (b / d) - (b / lc));
  cout << all - num1_c << endl;
  return 0;
}

Measured memory_bytes: 256
import sys
import itertools
import copy
from collections import defaultdict

input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N, K = MI()
    index = 0
    d = defaultdict(int)
    for i in range(N):
        a, b = MI()
        d[a] += b
    d = sorted(d.items(), key=lambda x:x[0])
    for i in d:
        index += i[1]
        if index >= K:
            print(i[0])
            sys.exit()
        
        
main()

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

#define debug(...) fprintf(stderr, __VA_ARGS__)

#ifndef AT_HOME
#define getchar() IO::myGetchar()
#define putchar(x) IO::myPutchar(x)
#endif

namespace IO {
	static const int IN_BUF = 1 << 23, OUT_BUF = 1 << 23;

	inline char myGetchar() {
		static char buf[IN_BUF], *ps = buf, *pt = buf;
		if (ps == pt) {
			ps = buf, pt = buf + fread(buf, 1, IN_BUF, stdin);
		}
		return ps == pt ? EOF : *ps++;
	}

	template<typename T>
	inline bool read(T &x) {
		bool op = 0;
		char ch = getchar();
		x = 0;
		for (; !isdigit(ch) && ch != EOF; ch = getchar()) {
			op ^= (ch == '-');
		}
		if (ch == EOF) {
			return false;
		}
		for (; isdigit(ch); ch = getchar()) {
			x = x * 10 + (ch ^ '0');
		}
		if (op) {
			x = -x;
		}
		return true;
	}

	inline int readStr(char *s) {
		int n = 0;
		char ch = getchar();
		for (; isspace(ch) && ch != EOF; ch = getchar())
			;
		for (; !isspace(ch) && ch != EOF; ch = getchar()) {
			s[n++] = ch;
		}
		s[n] = '\0';
		return n;
	}

	inline void myPutchar(char x) {
		static char pbuf[OUT_BUF], *pp = pbuf;
		struct _flusher {
			~_flusher() {
				fwrite(pbuf, 1, pp - pbuf, stdout);
			}
		};
		static _flusher outputFlusher;
		if (pp == pbuf + OUT_BUF) {
			fwrite(pbuf, 1, OUT_BUF, stdout);
			pp = pbuf;
		}
		*pp++ = x;
	}

	template<typename T>
	inline void print_(T x) {
		if (x == 0) {
			putchar('0');
			return;
		}
		static int num[40];
		if (x < 0) {
			putchar('-');
			x = -x;
		}
		for (*num = 0; x; x /= 10) {
			num[++*num] = x % 10;
		}
		while (*num){
			putchar(num[*num] ^ '0');
			--*num;
		}
	}

	template<typename T>
	inline void print(T x, char ch = '\n') {
		print_(x);
		putchar(ch);
	}

	inline void printStr_(const char *s, int n = -1) {
		if (n == -1) {
			n = strlen(s);
		}
		for (int i = 0; i < n; ++i) {
			putchar(s[i]);
		}
	}

	inline void printStr(const char *s, int n = -1, char ch = '\n') {
		printStr_(s, n);
		putchar(ch);
	}
}
using namespace IO;

int n, x[55], y[55];

int main() {
	read(n);
	for (int i = 1; i <= n; ++i) {
		read(x[i]), read(y[i]);
	}
	int ans = n;
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			int s = 0;
			for (int k = 1; k <= n; ++k) {
				bool flag = 1;
				for (int l = 1; l <= n; ++l) {
					if (x[k] - x[l] == x[i] - x[j] && y[k] - y[l] == y[i] - y[j]) {
						flag = 0;
					}
				}
				s += flag;
			}
			ans = std::min(ans, s);
		}
	}
	print(ans);
}


Measured memory_bytes: 3552
def count(n):
    return sum(map(lambda x: int(x), str(n)))


N = int(input())
ret = float('inf')
for i in range(1, N + 1):
    A = i
    B = N - i
    if A > B:
        break

    ret = min(ret, count(A) + count(B))

print(ret)


Measured memory_bytes: 2940
N, K = map(int, input().split())
mod = 998244353
lr = [0] * K
for i in range(K):
    lr[i] = list(map(int, input().split()))
    lr[i][1] += 1

dp = [0] * (N+1)
dp[1] = 1
s = 0
for i in range(1, N):
    s += dp[i]
    for j in range(K):
        if (i + lr[j][0]) <= N:
            dp[i + lr[j][0]] = (dp[i + lr[j][0]] + s) % mod
        if (i + lr[j][1]) <= N:
            dp[i + lr[j][1]] = (dp[i + lr[j][1]] - s) % mod
        

print(dp[N])

Measured memory_bytes: 75252
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	cin>> n;
	int p= n % 10;
	if(p==2 || p==4 || p==5 || p==7 || p==9) cout<< "hon";
	if(p==0 || p==1 || p==6 || p==8) cout<< "pon";
	if(p==3) cout<< "bon";
	return 0;
}

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

using namespace std;
using ll = long long;


int main()
{
    int n;cin >> n;
    for(int i = 0;i < n;i++){
        string s;cin >> s;
        set<string> ans;
        for(int j = 1;j < s.size();j++){
            string a = s.substr(0, j);
            string b = s.substr(j, s.size());
            string c = a;
            string d = b;
            reverse(a.begin(), a.end());
            reverse(b.begin(), b.end());
            ans.insert(a + b);
            ans.insert(a + d);
            ans.insert(b + a);
            ans.insert(d + a);
            ans.insert(c + b);
            ans.insert(c + d);
            ans.insert(b + c);
            ans.insert(d + c);
        }

        ans.insert(s);
        reverse(s.begin(), s.end());
        ans.insert(s);
     //   for(auto a : ans)cout<<a<<endl;
        cout<<ans.size()<<endl;
    }
}



Measured memory_bytes: 3260
#include <cstdio>

using namespace std;

int main()
{
	int a,b,cnt=0;
	int sum=0,ave=0;
	
	while(~scanf("%d,%d",&a,&b)){
		sum+=(a*b);
		ave+=b;
		cnt++;
	}
	printf("%d\n%d\n",sum,(int)(ave/(double)cnt+0.5));
	return 0;
}

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

using namespace std;
int G[400][400];
int R[400][400];
int used[400][400];
int main()
{
    memset(used,0,sizeof(used));
    int N;
    cin>>N;
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            cin>>G[i][j];
            R[i][j] = G[i][j];
        }
    }
    for(int k=1; k<=N; k++)
    {
        for(int i=1; i<=N; i++)
        {
            for(int j=1; j<=N; j++)
            {
                R[i][j] = min(R[i][j],R[i][k]+R[k][j]);
                if(G[i][j] == G[i][k] + G[k][j] && k!=i && k!=j)
                {
                    used[i][j] = 1;
                }
            }
        }
    }
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            if(G[i][j] != R[i][j])
            {
                cout<<-1<<endl;
                return 0;
            }
        }
    }

    long long ans =0;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            if(!used[i][j])
            {
                ans += G[i][j];
            }
        }
    }
    ans/=2;
    cout<< ans<<endl;



}


Measured memory_bytes: 1792
#include <iostream>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;

    string s2 = "";
    for (size_t i = 0; i < s.size(); i++) {
        s2 += s[s.size()-i-1];
    }
    
    string s3 = "";
    for (int i = 0; i < s.size(); i++) {
        if (s2[i] == 'b') {
            s3 += 'd';
        }
        if (s2[i] == 'd') {
            s3 += 'b';
        }
        if (s2[i] == 'p') {
            s3 += 'q';
        }
        if (s2[i] == 'q') {
            s3 += 'p';
        }
    }
    
    bool ok = true;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] != s3[i]) {
            ok = false;
        }
    }
    cout << (ok ? "Yes" : "No") << endl;
    
}

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

int main() {
    int a, b, k;
    cin >> a >> b >> k;
    vector<int> v;
    for (int i = 1; i <= min(a, b); i++) {
        if (a % i == 0 && b % i == 0) {
            v.push_back(i);
        }
    }
    int n = v.size();
    cout << v[n - k] << '\n'; 
}

Measured memory_bytes: 3628
import math
import itertools
import sys
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, M, R = IL()
r = IL()
abc = [IL() for _ in range(M)]

dp = [[MAX_INT]*(N+1) for _ in range(N+1)]
for a, b, c in abc:
  dp[a][b] = c
  dp[b][a] = c

for k in range(1, N+1):
  for i in range(1, N+1):
    for j in range(1, N+1):
      if i == j:
        dp[i][j] = 0
      else:
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
#print(dp)

ans = MAX_INT
for root in itertools.permutations(r):
  tmp = 0
  for i in range(R-1):
    tmp += dp[root[i]][root[i + 1]]
  else:
    ans = min(ans, tmp)
print(ans)

Measured memory_bytes: 49496
#include <iostream>

using namespace std;

int main() {
    int N, temp, max, l, output;
    output = 1;
    max = 0;
    cin >> N;
    
    for( int i = 1; i <= N; i++ ) {
        temp = i;
        for( l = 1; true; l++ ) {
            if( temp % 2 != 0 ) {
                break;
            }
            temp = temp / 2;
        }
        if( l-1 >= max ) {
            max = l-1;
            output = i;
        }
    }
    
    cout << output << endl;

    return 0;
}

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

namespace Test
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            string s = Console.ReadLine();
            bool flag = true;
            int i;
            for (i = 0; i < x[0]; i++)
            {
                if (s[i] < '0' || '9' < s[i]) flag = false;
            }
            if (s[i] != '-') flag = false;
            i++;
            for (; i < x[0] + 1 + x[1]; i++)
            {
                if (s[i] < '0' || '9' < s[i]) flag = false;
            }
            Console.WriteLine(flag ? "Yes" : "No");
        }
    }
}

Measured memory_bytes: 13268
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>

#define MAX_V 3010
#define INF 100000000000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
struct edge {int to; ll cap, cost, rev;};
vector<edge> G[MAX_V],H[MAX_V];
ll V,h[MAX_V],dist[MAX_V],prevv[MAX_V],preve[MAX_V];
void add_edge(int from, int to, ll cap, ll cost){
	G[from].push_back((edge){to, cap, cost, (ll)G[to].size()});
	G[to].push_back((edge){from, 0, -cost, (ll)G[from].size() - 1});
}

ll min_cost_flow(int s,int t, ll f){
	ll res = 0;
	fill(h,h + V,INF);
	h[s] = 0;
	while(true){
		bool upd = false;
		for(int i=0;i<V;i++){
			for(edge e:G[i]){
				if(h[i]==INF || e.cap==0) continue;
				if(h[e.to]>h[i] + e.cost){
					h[e.to] = h[i] + e.cost;
					upd = true;
				}
			}
		}
		if(!upd) break;
	}
	int cnt = 0;
	while(f>0){
		priority_queue<pll,vector<pll>,greater<pll>> que;
		fill(dist,dist + V,INF);
		que.push({0,s});
		dist[s] = 0;
		while(que.size()){
			pll p = que.top(); que.pop();
			if(dist[p.second]<p.first) continue;
			for(int i=0;i<G[p.second].size();i++){
				edge e = G[p.second][i];
				if(e.cap>0 && dist[e.to] > dist[p.second] + e.cost + h[p.second] - h[e.to]){
					dist[e.to] = dist[p.second] + e.cost + h[p.second] - h[e.to];
					prevv[e.to] = p.second;
					preve[e.to] = i;
					que.push({dist[e.to],e.to});
				}
			}
		}
		if(dist[t]==INF) return -1;
		for(int v=0;v<V;v++) h[v] += dist[v];
		ll d = f;
		for(int v = t; v!=s; v = prevv[v]){
			d = min(d,G[prevv[v]][preve[v]].cap);
		}
		f -= d;
		res += d*h[t];
		for(int v = t; v!=s; v = prevv[v]){
			edge &e = G[prevv[v]][preve[v]];
			e.cap -= d;
			G[v][e.rev].cap += d;
		}
	}
	return res;
}

ll a[1010],b[1010];
map<ll,int> mp;
int main(){
	int i,n;
	cin >> n;
	int cnt = n + 1;
	for(i=1;i<=n;i++){
		cin >> a[i] >> b[i];
		if(mp[a[i]]==0){
			mp[a[i]] = cnt;
			cnt++;
		}
		if(mp[b[i]]==0){
			mp[b[i]] = cnt;
			cnt++;
		}
	}
	V = cnt + 1;
	for(i=1;i<=n;i++){
		add_edge(0,i,1,0);
		add_edge(i,mp[b[i]],1,-a[i]);
		add_edge(i,mp[a[i]],1,-b[i]);
	}
	for(i=n + 1;i<cnt;i++){
		add_edge(i,cnt,1,0);
	}
	add_edge(0,V - 1,INF,0);
	cout << -min_cost_flow(0,V - 1,n) << endl;
}


Measured memory_bytes: 3952
#include<bits/stdc++.h>
#define dd(x) cout<<#x<<" = "<<x<<" "
#define de(x) cout<<#x<<" = "<<x<<"\n"
#define sz(x) int(x.size())
#define All(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef priority_queue<int> BQ;
typedef priority_queue<int,vector<int>,greater<int> > SQ;
const int maxn=3e5+10,mod=1e9+7,INF=0x3f3f3f3f;

int main()
{
	int k,a,b;
  cin>>k>>a>>b;
  vector<int> v;
  for (int i=a;i<=b;++i)
    v.pb(i);
  for (auto i:v)
    if (i%k==0){
      cout<<"OK";
      return 0;
    }
 	cout<<"NG";
	return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
#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++)

using namespace std;
 

int main() {
  int Q;
  cin>>Q;
  
  vector<int>l(Q);
  rep(i,Q) {    
    cin >> l.at(i);  
  }
  int to=abs(l.at(0))+abs(l.at(Q-1));
  rep2(i,1,Q){
    to+=abs(l.at(i)-l.at(i-1));
  }
  cout<<to+abs(l.at(1)-0)-(abs(l.at(1)-l.at(0))+abs(l.at(0)-0))<<endl;
  rep2(i,1,Q-1) {    
    cout<<to+abs(l.at(i+1)-l.at(i-1))-(abs(l.at(i+1)-l.at(i))+abs(l.at(i)-l.at(i-1)))<<endl;
  }
  cout<<to+abs(l.at(Q-2)-0)-(abs(l.at(Q-2)-l.at(Q-1))+abs(l.at(Q-1)-0))<<endl;
}

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

int main(){
	char b;
	cin >> b;

	if(b=='A') cout << 'T' << endl;
	else if(b=='T') cout << 'A' << endl;
	else if(b=='C') cout << 'G' << endl;
	else cout << 'C' << endl;

	return 0;
}

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

#include <iostream>
#include <string>

#include <algorithm>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <vector>

#define PB push_back
#define MP make_pair

#define FOR(i, b, e) for(int i=(b);i<(e);i++)
#define REP(i, n) FOR(i,0,n)

#define ALL(v) (v).begin(),(v).end()

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

typedef pair<int, int> PII;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VPII;

const int MOD = 1000000009;
const int INF = 1e9;

const double EPS = 1e-9;
const double PI = acos(-1.0);

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 N, K;

int main() {
    cin >> N >> K;
    double sum = 0.0;
    REP (i, N) {
        int prod = N;
        for (int tmp = i + 1; tmp < K; tmp *= 2) {
            prod *= 2;
        }
        sum += 1.0 / prod;
    }
    printf("%.12f\n", sum);
    return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())

l = m // 2 * 2 + 1
for i in range(1, l + 1):
    if i < l - i + 1:
        print(i, l - i + 1)

r = (m + 1) // 2 * 2 + l
for i in range(l + 1, r + 1):
    if i < r - i + l + 1:
        print(i, r - i + l + 1)


Measured memory_bytes: 9284
n = int(input())
x = list(map(int, input().split()))

if (len(set(x)) == 1):
  print(0)
else:
  ans = []
  for p in range(min(x), max(x)):
    sigma = 0
    for i in x:
      sigma += (p-i)**2
    ans.append(sigma)
  print(min(ans))

Measured memory_bytes: 38640
# 2019-11-19 10:28:31(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    count = 1
    for i in range(n-1):
        if s[i+1] != s[i]:
            count += 1
    print(count)

if __name__ == "__main__":
    main()


Measured memory_bytes: 3316
X,Y = list(map(int,input().split()))

count = 0

if X == 1 and Y == 1:
    count = 400000
    
if X == 1:
    count += 300000
elif X == 2:
    count += 200000
elif X == 3:
    count += 100000
    
if Y == 1:
    count += 300000
elif Y == 2:
    count += 200000
elif Y == 3:
    count += 100000
    
print(count)

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

using namespace std;

//FILE *fi=freopen("1.txt","r",stdin);

int n,m,q;
long long a[301][301],L,d[301][301];

void floyd()
{
    for (int k=1;k<=n;++k)
    {
        for (int u=1;u<=n;++u)
        {
            for (int v=1;v<=n;++v)
            {
                if (a[u][v]>a[u][k]+a[k][v])
                {
                    a[u][v]=a[u][k]+a[k][v];
                }
            }
        }
    }
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=n;++j)
        {
            if (a[i][j]<=L)
                d[i][j]=1;
            else d[i][j]=INT_MAX;
        }
    }
    for (int k=1;k<=n;++k)
    {
        for (int u=1;u<=n;++u)
        {
            for (int v=1;v<=n;++v)
            {
                if (d[u][v]>d[u][k]+d[k][v])
                {
                    d[u][v]=d[u][k]+d[k][v];
                }
            }
        }
    }
}

void nhap()
{
    scanf("%d %d %lld",&n,&m,&L);
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=n;++j)
        {
            if (i!=j)
                a[i][j]=INT_MAX;
        }
    }
    for (int i=1;i<=m;++i)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        a[u][v]=a[v][u]=w;
    }
    floyd();
    scanf("%d",&q);
    while (q--)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        if (d[u][v]!=INT_MAX)
            cout<<d[u][v]-1<<"\n";
        else cout<<-1<<"\n";
    }
}

int main()
{
    nhap();
    return 0;
}


Measured memory_bytes: 1920
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    long x;
    scanf("%ld", &x);
    if(x >= 30){
        printf("Yes");
    }
    else {
        printf("No");
    }
    
    return 0;
}


Measured memory_bytes: 3228
from collections import deque
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)

ans=0
d=deque([a[0]])
for i in range(1,len(a)):
  d.append(a[i])
  d.append(a[i])
  ans+=d.popleft()
print(ans)

Measured memory_bytes: 32428
#include<bits/stdc++.h>
//using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i,a,b) for (int i=(a);i<(b);i++)
#define per(i,a,b) for (int i=(b)-1;i>=a;i--)
#define sz(a) (int) a.size()
#define de(a) cout<<#a<<" = "<<a<<endl
#define dd(a) cout<<#a<<" = "<<a<<" "
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
//-----
const int N = 2e5+7;
int a[N];
int main() {
    int n,t;
    ll f1,f2,f3;
    while(scanf("%d",&n) != EOF) {
        ll all = 0,ans = 0;
        f1 = 0,f2 = 0,f3 = 0;
        rep(i,1,n+1) {
            scanf("%d",&t);all += t;
            if(t == 0) {
                f3 = max(0LL,max(f2,f3) - 2);
                f2 = max(0LL,max(f1,f2) - 1);
                f1 = max(0LL,f1 - 2);
            }else if(t & 1) {
                f3 = max(0LL,max(f2,f3) - 1 + t);
                f2 = max(0LL,max(f1,f2) + t);
                f1 = max(0LL,f1 + t - 1);
            }else {
                f3 = max(0LL,max(f2,f3) + t);
                f2 = max(0LL,max(f1,f2) + t - 1);
                f1 = max(0LL,f1 + t);
            }
            ans = max(max(ans,f1),max(f2,f3));
            //dd(f1),dd(f2),de(f3);
        }
        printf("%lld\n",all - ans);
    }
    return 0;
}



Measured memory_bytes: 256
n, m = map(int,input().split())
li = []
ans = []
for i in range(n):
    x, y, z = map(int,input().split())
    li.append([x, y, z])

li000 = []
for i in range(n):
    li000.append(li[i][0]+li[i][1]+li[i][2])

li000_sort = sorted(li000,reverse=True)

ans000 = 0
for i in range(m):
    ans000 += li000_sort[i]
ans.append(ans000)


li001 = []
for i in range(n):
    li001.append(li[i][0]+li[i][1]-li[i][2])

li001_sort = sorted(li001,reverse=True)

ans001 = 0
for i in range(m):
    ans001 += li001_sort[i]
ans.append(ans001)


li010 = []
for i in range(n):
    li010.append(li[i][0]-li[i][1]+li[i][2])

li010_sort = sorted(li010,reverse=True)

ans010 = 0
for i in range(m):
    ans010 += li010_sort[i]
ans.append(ans010)


li011 = []
for i in range(n):
    li011.append(li[i][0]-li[i][1]-li[i][2])

li011_sort = sorted(li011,reverse=True)

ans011 = 0
for i in range(m):
    ans011 += li011_sort[i]
ans.append(ans011)


li100 = []
for i in range(n):
    li100.append(-li[i][0]+li[i][1]+li[i][2])

li100_sort = sorted(li100,reverse=True)

ans100 = 0
for i in range(m):
    ans100 += li100_sort[i]
ans.append(ans100)


li101 = []
for i in range(n): #101
    li101.append(-li[i][0]+li[i][1]-li[i][2])

li101_sort = sorted(li101,reverse=True)

ans101 = 0
for i in range(m):
    ans101 += li101_sort[i]
ans.append(ans101)


li110 = []
for i in range(n): #110
    li110.append(-li[i][0]-li[i][1]+li[i][2])

li110_sort = sorted(li110,reverse=True)

ans110 = 0
for i in range(m):
    ans110 += li110_sort[i]
ans.append(ans110)


li111 = []
for i in range(n): #111
    li111.append(-li[i][0]-li[i][1]-li[i][2])

li111_sort = sorted(li111,reverse=True)

ans111 = 0
for i in range(m):
    ans111 += li111_sort[i]
ans.append(ans111)


print(max(ans))

Measured memory_bytes: 3700
n=gets.chomp.to_i
h=gets.chomp.split.map(&:to_i)
ans=[]
tmp=0
for i in 0..n-2
  if h[i]>=h[i+1]
    tmp+=1
  else
    ans << tmp
    tmp=0
  end
end
ans << tmp
p ans.max


Measured memory_bytes: 9860
#!/usr/bin/env python3

def main():
    N = int(input())
    pa = []
    for i in range(N):
        s = input().split()
        a, b = int(s[0]), int(s[1])
        pa.append((0, a, b))
    for i in range(N):
        s = input().split()
        c, d = int(s[0]), int(s[1])
        pa.append((1, c, d))

    pa.sort(key = lambda v: v[1])

    c = 0
    st = []
    for v in pa:
        if v[0] == 0:
            if len(st) == 0 or st[-1][2] > v[2]:
                st.append(v)
            else:
                for i, w in enumerate(st):
                    if v[2] > w[2]:
                        st.insert(i, v)
                        break
        else:
            for i in range(len(st)):
                if v[2] > st[i][2]:
                    st.pop(i)
                    c += 1
                    break


    print(c)


if __name__ == '__main__':
    main()



Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <queue>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define fr(i,k,N) for(ll i=k; i<N;i++)
#define rep(i,N) for(ll i=0; i<N;i++)
#define alll(v) v.begin(),v.end()
using namespace std;
template <class X> void pr(X test){cout<<test<<endl;}
template <class X> void prr(X test){for(auto it:test){cout<<it<<endl;}cout<<endl;}

int main() {
    ll a,b,c,d,e,f;
    cin >>a>>b>>c>>d>>e>>f;
    map<ll,ll> m;
    m[a]+=1;
    m[b]+=1;
    m[c]+=1;
    m[d]+=1;
    m[e]+=1;
    m[f]+=1;
    bool t = true;
    for(auto it:m){
        if(it.second >= 3) t = false;
    }
    if(m[1] == 0) t = false;
    if(m[2] == 0) t = false;
    if(m[3] == 0) t = false;
    if(m[4] == 0) t = false;
    cout<<(t ? "YES" : "NO")<<endl;
    
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#include<numeric>
using namespace std;

int main(){
    string s;
    cin >> s;
    int N = s.length();
    int x, y;
    cin >> x >> y;
    int nf=0;
    for(int i = 0; i < N; ++i) {
        if(s[i]=='F'){
            x--;
            nf++;
        }
        else{
            break;
        }
    }
    if(nf==N || nf==N-1){
        if(x == 0 && y == 0)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
        return 0;
    }

    vector<int> ys(1,0);
    vector<int> xs(1,0);
    bool xaxis = false;
    int f=0;
    for(int i = nf+1; i < N; ++i) {
        if(s[i]=='T') {
            if(xaxis)
                xs.push_back(2*f);
            else{
                ys.push_back(2*f);
            }
            xaxis = !xaxis;
            f=0;
        }else{ // F
            f++;
        }
    }
    if(xaxis)
        xs.push_back(2*f);
    else{
        ys.push_back(2*f);
    }
    int xsum = accumulate(xs.begin(), xs.end(), 0);
    int ysum = accumulate(ys.begin(), ys.end(), 0);
    xsum = xsum/2 - x;
    ysum = ysum/2 - y;
    if (ysum < 0 || xsum < 0){
        cout << "No" << endl;
        return 0;
    }
    //dp, using ith number tu sum up j
    int max = 16000;
    vector<vector<bool> > dp(xs.size(), vector<bool>(max, false));
    dp[0][0] = dp[0][xs[0]] = true;
    for(int i = 1; i < xs.size(); ++i) { // using ith
        for(int j = 0; j < max; j+=2) { // sum = j
            if (dp[i-1][j] || (j-xs[i] >= 0 && dp[i-1][j-xs[i]]))
                dp[i][j] = true;
        }
    }
    vector<vector<bool> > dpy(ys.size(), vector<bool>(max, false));
    dpy[0][0] = dpy[0][ys[0]] = true;
    for(int i = 1; i < ys.size(); ++i) { // using ith
        for(int j = 0; j < max; j+=2) { // sum = j
            if (dpy[i-1][j] || (j-ys[i] >= 0 && dpy[i-1][j-ys[i]]))
                dpy[i][j] = true;
        }
    }
    if (dp.back()[xsum] && dpy.back()[ysum])
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
 
int main() {
int N;
  cin >> N;
  vector<int> vec(N);
  for(int i =0;i < N; i++){
    cin >> vec.at(i);}
  sort(vec.begin(), vec.end());
  int d = 1;
  for(int i =0; i < N - 1;i++){
    if(vec.at(i) != vec.at(i+1)){
      d++;}}
  cout << d << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(ll i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(ll i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
vi mem;
int dfs(int x){
    if(x==0){
        return 0;
    }
    if(mem[x]!=-1){
        return mem[x];
    }
    int res=INF;
    int k=1;
    while(k<=x){
        chmin(res,dfs(x-k)+1);
        k*=6;
    }
    k=1;
    while(k<=x){
        chmin(res,dfs(x-k)+1);
        k*=9;
    }
    return mem[x]=res;
}
int main(){
    int n;
    cin>>n;
    mem.resize(n+1,-1);
    cout<<dfs(n)<<endl;
    return 0;
}

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

using namespace std;

using ll = long long;
using ld = long double;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    int n;
    cin >> n;

    vector<ll> s(n);
    for (auto &s_i : s) cin >> s_i;

    ll max_score = 0;
    vector<int> visited(n);
    for (int c = 1; c <= n - 1; ++c) {
        ll sum = 0;

        for (int k = 0; (k + 1) * c < n - 1; ++k) {
            if (k * c == n - 1 - k * c) break;
            if (visited[k * c] == c or visited[n - 1 - k * c] == c)
                break;
            visited[k * c] = visited[n - 1 - k * c] = c;

            sum += (s[k * c] + s[n - 1 - k * c]);
            max_score = max(max_score, sum);
        }
    }

    cout << max_score << endl;

    return 0;
}


Measured memory_bytes: 1408