akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <climits>
#include <map>
#include <functional>
#include <cmath>
#include <cassert>

using namespace std;

template <typename T>
int bisect_right(const std::vector<T>& arr, T target)
{
  int lo = 0;
  int hi = arr.size();

  while (lo < hi) {
      int mid = (lo + hi)/2;

      if (arr[mid] > target) {
          hi = mid;
      } else {
          lo = mid + 1;
      }
  }
  return lo;
}

#define DUMP(a) do { cout << #a << "={"; for (int i = 0; \
                i < a.size(); i++) cout << a[i] << " "; \
                cout << "}" << endl; } while (0)

int main()
{
    vector<int> t = { 0, 1, 2, 3, 4, 5, 6 };

    int n; cin >> n;
    vector<int> a(n), b(n), c(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = 0; i < n; i++) cin >> c[i];
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    sort(c.begin(),c.end());

    vector<long> aa(n+1), bb(n+1);

    for (int i = n - 1; i >= 0; i--) {
        int j = bisect_right(c, b[i]);
        bb[i] = bb[i+1] + (n-j);
    }
    for (int i = n - 1; i >= 0; i--) {
        int j = bisect_right(b, a[i]);
        aa[i] = aa[i+1] + bb[j];
    }

    // DUMP(aa);
    // DUMP(bb);
    // DUMP(cc);

    cout << aa[0] << endl;
    return 0;
}

Measured memory_bytes: 2944
// clang-format off
#include <bits/stdc++.h>

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount
#define ffs __builtin_ffs
#define ctz __builtin_ctz
#define clz __builtin_clz
#define all(a) (a).begin(), (a).end()
 
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pil = pair<int,ll>;
using pll = pair<ll,ll>;
template <typename T> using vec = vector<T>;
using vi = vec<int>;
using vl = vec<ll>;
template <typename T> using que = queue<T>;
template <typename T> using deq = deque<T>;

template <typename T> T id(T b) {return b;};
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}
template <typename S, typename K> bool contains(S &s, K k) { return s.find(k) != s.end(); }
void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); }
constexpr ll TEN(int n) { if (n == 0) return 1LL; else return 10LL*TEN(n-1); }
// clang-format on

ll dp[300 * 300 + 1];
int h, w, d;
pii pos[300 * 300 + 1];

ll mdist(int x, int y) {
    auto a = pos[x];
    auto b = pos[y];
    return abs(a.fst - b.fst) + abs(a.snd - b.snd);
}

int main() {
    fastio();

    cin >> h >> w >> d;
    forn(i, h) forn(j, w) {
        int a;
        cin >> a;
        pos[a] = mp(i, j);
    }

    for (int i = 1; i <= h * w; i++) {
        if (i - d > 0) {
            dp[i] = dp[i - d] + mdist(i, i - d);
            //cout << i << " " << dp[i] << endl;
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;

        cout << dp[r] - dp[l] << "\n";
    }

    return 0;
}

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

#define       sf                 scanf
#define       pf                 printf
#define       pb                 push_back
#define       sz                 200005
#define       inf                0x3f3f3f3f
#define       MOD                1000000007
#define       READ               freopen("in.txt", "r", stdin);
#define       WRITE              freopen("out.txt", "w", stdout);
#define       optimize           ios::sync_with_stdio(0);cin.tie(0);

using namespace std;

typedef       long long int      ll;

int main()
{
    // READ
    optimize

    int n, a[sz];

    cin >> n;

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

   	sort(a, a+n);

   	int cn = n-1; 

   	ll ans = a[n-1]; cn--;

   	for(int i = n-2; i >= 0; i--)
   	{
   		if(cn==0) break;
   		ans += ll(a[i]); cn--;

   		if(cn==0) break;
   		ans += ll(a[i]);cn--;
   	}

   	cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4436
x=input()
p=len(x)
n=int(x)
s=0
c=int(x)
for i in range(p):
    
    rem=n%10
    n=n/10
    s=(s*10)+int(rem)
    n=int(n)
    
    
   
   
if (c==s):
    print('Yes')
else:
    print('No')
    

    
    

    


Measured memory_bytes: 3060
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
q = int(input())
ans = sum(A)
A = Counter(A)
for i in range(q):
    b, c = map(int, input().split())
    ans += (c-b)*A[b]
    print(ans)
    A[c] += A[b]; A[b] = 0

Measured memory_bytes: 23388
import java.util.Scanner

import scala.collection.mutable


object Main {

  def main(args: Array[String]): Unit = {

    val sc = new Scanner(System.in)
    val n = sc.nextInt() //temboudai
    val m = sc.nextInt() //road count

    val h = Vector.fill(n)(sc.nextInt()) //high
    val ab = Vector.fill(m)((sc.nextInt(), sc.nextInt())) //road


    val bads = mutable.Set.empty[Int]

    def l(a: Int, b: Int): Unit = {
      (h(a - 1), h(b - 1)) match {
        case (ha, hb) if ha > hb => bads += b
        case (ha, hb) if ha < hb => bads += a
        case _ => bads += a += b
      }
    }

    ab.foreach { case (a, b) => l(a, b) }
    println((1 to n).count(!bads.contains(_)))
  }

}


Measured memory_bytes: 67472
#include<string.h>
#include<iostream>
int main()
{
	char W[11];
	std::cin >> W;
	while(true)
	{
		static int cnt = 0;
		char Ti[1001];
		std::cin >> Ti;
		bool is_OK = true;
		for(int i = 0; i == 0 || W[i - 1] != '\0'; i++)
		{
			is_OK &= W[i] == Ti[i] || W[i] == Ti[i] - 'A' + 'a';
		}
		if(is_OK)
		{
			cnt++;
		}
		if(strcmp(Ti, "END_OF_TEXT") == 0)
		{
			std::cout << cnt << std::endl;
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
typedef long long ll;
long long mod = 1e9 + 7;
const int iINF = 0x3f3f3f3f;
const long long INF = 1LL << 60;
using namespace std;
using pint = pair<int, int>;

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

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

char g[110][110];
int ans = iINF;
int h_max, w_max;

int main()
{

  cin >> h_max >> w_max;

  int dp[110][110];

  rep(i, h_max) rep(j, w_max)
  {
    cin >> g[i][j];
    dp[i][j] = iINF;
  }

  ;
  dp[0][0] = g[0][0] == '#' ? 1 : 0;

  int dx[2] = {1, 0};
  int dy[2] = {0, 1};

  rep(i, h_max) rep(j, w_max)
  {
    rep(k, 2)
    {
      int next_i = i + dx[k];
      int next_j = j + dy[k];

      if (next_i >= h_max || next_j >= w_max)
        continue;

      int count = 0;
      if (g[i][j] == '.' && g[next_i][next_j] == '#')
        count++;
      chmin(dp[next_i][next_j], dp[i][j] + count);
    }
  }

  cout << dp[h_max - 1][w_max - 1] << endl;
  return 0;
}

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

int main()
{
	int n, K, l = 0, r = 0, P;
	scanf("%d %d", &n, &K);
	vector<int> w(n);
	for (int &x: w) {
		scanf("%d", &x);
		l = l > x ? l : x;
		r += x;
	}
	P = (r - l) / n + l;
	while (l != r) {
		auto i = w.begin(), e = w.end(), ee = e - 1;
		int k = 0, p = 0;
		for (; i != e && k < K; i++) {
			int t = p + *i;
			if (t < P)
				p = t;
			else if (t > P)
				p = *i, k++;
			else {
				p = 0;
				if (i != ee)
					k++;
			}
		}
		if (i == e && k < K)
			r = P;
		else
			l = P + 1;
		P = (l + r) / 2;
	}
	printf("%d\n", r);
}



Measured memory_bytes: 2748
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define int long long
#define pb push_back
#define eb emplace_back
#define mp make_pair
const int MOD=1e9+7;
const int INF=1e15;

signed main(){
    int N,M;cin>>N>>M;
    vector<pair<int,int>>vec(N);
    REP(i,N){
        int a,b;cin>>a>>b;
        vec[i]=mp(a,b);
    }
    sort(vec.begin(),vec.end());
    priority_queue<int> que;
    int j=0;
    int ans=0;
    for(int i=M-1;i>=0;i--){
        while(j<=N&&vec[j].first==M-i){
            que.push(vec[j].second);
            j++;
        }
        if(!que.empty()){
			ans+=que.top();
        	que.pop();
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 2936
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i,n) for (int i = 0; i < n; ++i)
#define REP(i,k,n) for (int i = k; i <= n; ++i)
#define REPR(i,k,n) for (int i = k; i >= n; --i)
#define pb push_back
#define F first
#define S second
#define I insert
#define mp make_pair
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
#define debug1(a) cout<<" "<<#a<<" : "<<a<<"\n"
#define debug2(a,b) cout<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<"\n"
#define debug3(a,b,c) cout<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<" "<<#c<<" : "<<c<<"\n"
#define debug4(a,b,c,d) cout<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<" "<<#c<<" : "<<c<<" "<<#d<<" : "<<d<<"\n"
// #define M 421412341324321
#define MOD 998244353

signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	
	int n,k;

	cin>>n>>k;
	string s;
	cin>>s;
	char pre = 'a';
	int c=1, cnt=0;
	rep(i,n)
	{
		if (s[i]==pre)
		{
			c++;
		}
		else
		{
			pre = s[i];
			cnt+=c-1;
			c=1;
		}
	}
	cnt+=c-1;
	int ans = min(n-1, cnt+2*k);
	cout<<ans;

}


Measured memory_bytes: 512
#include<iostream>
#include<vector>
using namespace std;
struct Mables{int num, color;};

int main(){
	for(;;){
		int n;
		vector<Mables> va;
		cin >> n;
		if(n == 0) break;
		for(int i = 0; i < n; i++){
			int a;
			cin >> a;
			if(i == 0){
				va.push_back((Mables){1, a});
				continue;
			}
			if(va.back().color == a){
				va.back().num++;
			}else{
				if(i % 2 == 0){
					va.push_back((Mables){1, a});
				}else{
					if(va.size() == 1){
						va.back().color = a;
						va.back().num++;
					}
					else{
						va[va.size() - 2].num += va[va.size() - 1].num + 1;
						va.pop_back();
					}
				}
			}
		}
		int ans = 0;
		for(int i = 0; i < va.size(); i++){
			if(va[i].color == 0) ans += va[i].num;
		}
		cout << ans << endl;
	}
	return 0;
}



Measured memory_bytes: 3064
import math

def combi(n, r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

def count(n, k, i):
    if n-k+1 < i:
        return 0
    return combi(n-k+1, i) * combi(k-1, i-1)

n, k = map(int, input().split())
for i in range(1, k+1):
    print(count(n, k, i) % (10**9+7))

Measured memory_bytes: 3316
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int main(){
    ll r;
    cin>>r;
    printf("%.2lf\n",2*r*M_PI);
    return 0;
}

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

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

ll calc(ll a, ll b, ll c) { return (a / b) * c + a % b; }

ll fst(ll N, vector<ll>& a, vector<ll>& b) {
	ll ret = N;
	for (ll g = 0; g <= N; ++g) {
		for (ll s = 0; s <= N; ++s) {
			ll br = N - (g + s);
			if (br < 0) { break; }
			ret = max(ret, calc(g, a[0], b[0]) + calc(s, a[1], b[1]) + calc(br, a[2], b[2]));
		}
	}
	return ret;
}

ll snd(ll N, vector<ll>& a, vector<ll>& b) {
	ll ret = N;
	for (ll x = 0; x <= N; ++x) {
		ll y = N - x;
		ret = max(ret, calc(x, a[0], b[0]) + calc(y, a[1], b[1]));
	}
	return ret;
}

int main() {
	ll N;
	cin >> N;
	vector<ll> A(3), B(3);
	for (int i = 0; i < 3; ++i) { cin >> A[i]; }
	for (int i = 0; i < 3; ++i) { cin >> B[i]; }
	
	vector<P> v(3);
	for (int i = 0; i < 3; ++i) { v[i] = P(B[i] - A[i], i); }
	sort(v.rbegin(), v.rend());
	vector<ll> a(3), b(3);
	for (int i = 0; i < 3; ++i) {
		a[i] = A[v[i].second];
		b[i] = B[v[i].second];
	}

	ll res = fst(N, a, b);
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	if (res == N) { res = fst(res, b, a); }
	else { res = snd(res, b, a); }
	cout << res << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main(){
    ll n,x; cin>>n>>x;
    vector<ll> a(n);
    rep(i,n) cin>>a[i];
    sort(a.begin(), a.end());
    ll res=0, tmp=0;
    rep(i,n){
        tmp+=a[i];
        if(tmp<=x) res++;
    }
    if(tmp<x) cout<<n-1<<endl;
    else cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

#define MAX_CHAR 1000

int main(){

    char num_as_char[MAX_CHAR + 1];
    unsigned int i = 0, sum = 0;

    while(1){

        scanf("%s", num_as_char);
        if(num_as_char[0] == '0') break;

        while (num_as_char[i] != '\0'){
            sum += num_as_char[i] - '0';
            i++;
        }

        printf("%d\n", sum);
        sum = 0;
        i = 0;
    
    }

    return 0;

}


Measured memory_bytes: 2684
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(int i=0;i<n;i++)
#define int long long
#define ggr getchar();getchar();return 0;
#define prique priority_queue
#define mod 1000000007
#define inf 1e15
#define key 1e9
using namespace std;
typedef pair<int, int>P;
void yes() { cout << "Yay!" << endl; }
void no() { cout << ":(" << endl; }
template<class T> inline void chmax(T& a, T b) {
	a = std::max(a, b);
}
template<class T> inline void chmin(T& a, T b) {
	a = std::min(a, b);
}
const int MAX = 330000;
int fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		finv[i] = finv[i - 1] * inv[i] % mod;
	}
}

// 二項係数計算
long long COMB(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
bool prime(int n) {
	int cnt = 0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0)cnt++;
	}
	if (cnt != 1)return false;
	else return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y)* mod_pow(kai(y, y), mod - 2, mod) % mod;
}
void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
struct edge { int to, cost; };
int par[114514], rrank[114514];//親、木の深さ
void init(int n) {
	rep(i, n) {
		par[i] = i;
		rrank[i] = 0;
	}
}
int find(int x) {
	if (par[x] == x) {
		return x;
	}
	else return par[x] = find(par[x]);
}
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	if (rrank[x] < rrank[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (rrank[x] == rrank[y])rrank[x]++;
	}
}
bool same(int x, int y) {
	return find(x) == find(y);
}
int n, k, s;
signed main() {
	cin >> n >> k >> s;
	rep(i, k)cout << s << " ";
	for (int i = k; i < n; i++) {
		if (s == key)cout << s - 1 << " ";
		else cout << s + 1 << " ";
	}
	ggr
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define print(x) cerr << (#x) << "is "<< x << "\n"
using ll = long long;
using pii = pair<int,int>;
const int MOD = 1e9+7, N = 1e5 + 10;

int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<ll> a(n),b;
	f(i,0,n){
		cin >> a[i];
		a[i] = a[i]*2;
	}
	ll aa = 0;
	b = a;
	f(i,0,n){
		if(i%2==0){
			aa += a[i];
		}else{
			aa -= a[i];
		}
	}
	aa = aa/2;
	vector<ll> res(n);
	res[0] = aa;
	f(i,1,n){
		res[i] = a[i-1]-res[i-1];
	}
	f(i,0,n){
		cout << res[i] << ' ';
	}
	return 0;
}

Measured memory_bytes: 3712
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long; 
int gcd(ll a,ll b){
    return b == 0 ? a : gcd(b,a%b);
}

int main()
{
	ll N,X;
	cin >> N>>X;
	auto x = vector<ll>(N+1,0);
	for(int i=0;i<N;i++){
	    cin >> x[i];
	}
	x[N]=X;
	sort(x.begin(),x.end());
	auto ret = x[1] - x[0];
	for(int i=1;i<N;i++){
	     ret = gcd(ret,x[i+1]-x[i]);
	}
	
	cout << ret;
}

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

int main() {
	ios_base::sync_with_stdio( false );

	int N;
	cin >> N;
	vector<int> d( N );
	for( auto& v: d ) { cin >> v; }

	int result = 0;
	for( int i = 0; i < N-1; ++i ) {
		for( int j = i+1; j < N; ++j ) {
			result += d[i] * d[j];
		}
	}

	cout << result << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < n; i++)
#define MOD 1000000007
using namespace std;
typedef long long ll;

int gcd(int a, int b) {
    if (a < b) swap(a, b);
    int r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

int main() {
    int N; cin >> N;
    vector<int> A(N);
    REP(i, 0, N) cin >> A[i];

    int ans = A[0];
    REP(i, 1, N) ans = gcd(ans, A[i]);
    cout << ans << endl;
    return 0;
}

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

class MainClass
{
    static void Main()
    {
        string s = Console.ReadLine();
        var ep = Console.ReadLine().Split().Select(_=>int.Parse(_)+8000).ToArray();
        
        var dpx = new SortedSet<int>();
        var dpy = new SortedSet<int>();

        int index = 0;
        int fx = 8000;
        while (index < s.Length && s[index] == 'F')
        {
            fx++;
            index++;
        }
        dpx.Add(fx);
        dpy.Add(8000);

        bool dir = false;

        while (index < s.Length)
        {
            while (index < s.Length && s[index] == 'T')
            {
                dir = !dir;
                index++;
            }

            int dist = 0;
            while (index < s.Length && s[index] == 'F')
            {
                dist++;
                index++;
            }

            if (dir)
            {
                var ny = new SortedSet<int>() ;
                foreach (var i in dpy)
                {
                    ny.Add(i - dist);
                    ny.Add(i + dist);
                }
                
                dpy = ny;
            }
            else
            {
                var nx = new SortedSet<int>();
                foreach (var i in dpx)
                {
                    nx.Add(i - dist);
                    nx.Add(i + dist);
                }
                dpx = nx;
            }
        }

        Console.WriteLine((dpx.Contains(ep[0]) && dpy.Contains(ep[1])) ? "Yes" : "No");
    }
}


Measured memory_bytes: 47256
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <tuple>

#define rep(i,n) for(ll i=0;i<n;i++)
#define dup(x,y) (((x)+(y)-1)/(y)) // dup * y >= x なる最小のdup.
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

using Graph = vector<vector<ll>>;
//	std::cout<<std::fixed<<std::setprecision(10);

struct Edge {
	int to, id;
};

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

	vector<vector<Edge>> G;
	vector<int> ans;

	G.resize(N);
	ans.resize(N-1);

	rep(i, N-1) {
		int a, b;
		cin >> a >> b;
		G[a-1].push_back((Edge){b-1, (int)i});
		G[b-1].push_back((Edge){a-1, (int)i});
	}

	/* wfs */
	queue<int> q;
	vector<int> used(N);
	vector<int> pre(N, -1); // そのnodeの親との辺の色
	q.push(0);
	used[0] = 1;
	while(!q.empty()) {
		int v = q.front();
		q.pop();
		// v の子に行く辺に色をつける
		int col = 1;
			
		rep(i, G[v].size()) {
			if(used[G[v][i].to]==1) continue;
			
			if(col==pre[v]) col++; 
			ans[G[v][i].id] = col;
			pre[G[v][i].to] = col;
			col++;

			q.push(G[v][i].to);
			used[G[v][i].to] = 1;
		}
	}

	int mx = 0;
	rep(i, N) mx = max(mx, int(G[i].size()));
	cout << mx << endl;

	rep(i, N-1) {
		cout << ans[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 7808
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <deque>
#define ll long long

using namespace std;

vector<int>S;
int cnt;

void merge(int left, int mid, int right) {
	vector<int>L(mid - left + 1), R(right - mid + 1);
	for (int i = 0; i < mid - left; i++) {
		L[i] = S[left + i];
	}
	for (int i = 0; i < right - mid; i++) {
		R[i] = S[mid + i];
	}
	L[mid - left] = 1010001000;
	R[right - mid] = 1010001000;
	int curL = 0;
	int curR = 0;
	for (int i = left; i < right; i++) {
		cnt++;
		if (L[curL] <= R[curR]) {
			S[i] = L[curL];
			curL++;
		}
		else {
			S[i] = R[curR];
			curR++;
		}
	}
}

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

int main() {
	int n; cin >> n;
	S.assign(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> S[i];
	}
	mergeSort(0, n);

	for (int i = 0; i < S.size(); i++) {
		if (i != 0)cout << " ";
		cout << S[i];
	}
	cout << endl << cnt << endl;



	return 0;
}





Measured memory_bytes: 6768
#include<bits/stdc++.h>
using namespace std;
#define ll long long
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n,m,num,ans,i,j,k,l,c,ni,nj;
	char ch[10][10];
	cin>>n>>m>>num;
	ans=0;
	for(i=0;i<n;i++) {
		for(j=0;j<m;j++) {
			cin>>ch[i][j];
		}
	}
	for(i=0;i<(1<<n);i++) {
		ni=i;
		int rarr[n]={0};
		for(int z=0;z<n;z++) {
			rarr[z]=ni%2;
			ni/=2;
		}
		for(j=0;j<(1<<m);j++) {
			nj=j;
			int carr[m]={0};
			for(int z=0;z<m;z++) {
				carr[z]=nj%2;
				nj/=2;
			}
			c=0;
			for(k=0;k<n;k++) {
				if(rarr[k]==1) continue;
				for(l=0;l<m;l++) {
					if(carr[l]==1) continue;
					if(ch[k][l]=='#') c++;
				}
			}
			if(c==num) ans++;
		}
	}
	cout<<ans;
}

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

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> a(n, vector<int>(m, 0));
  vector<int> b(m, 0), c(n, 0);
  
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }
  for (int j = 0; j < m; j++) cin >> b[j];
  
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      c[i] += a[i][j]*b[j];
    }
  cout << c[i] << "\n";
  }
  
  return 0;
}

Measured memory_bytes: 1252
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define MA(i,j) make_pair(i,j)
#define PA pair<int,int>
#define PB push_back
#define PQ priority_queue<int>
#define PGQ priority_queue<int,vector<int>,greater<int> >
#define VE vector<int>
#define VP vector<PA>
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define MOD 1000000007
#define INF 1000000007
using namespace std;
//
int main(){
  int N;
  int sum=0;
  PGQ que;
  cin>>N;
  FOR(i,0,N){
    int S;
    cin>>S;
    if(S%10){
      que.push(S);
    }
    sum+=S;
  }
  if(sum%10){
    cout<<sum<<endl;
  }else{
    if(que.size()){
      cout<<sum-que.top()<<endl;
    }else{
      cout<<"0"<<endl;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x ,n) for(int i = x; i < n; i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main(){
    int n;
    cin >> n;
    int sn=0;
    int np = n;
    while(np){
        sn+=np%10;
        np/=10;
    }
    
    if(n%sn==0)cout << "Yes";
    else cout << "No";
    
	return 0;
}

Measured memory_bytes: 3580
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;
using System.Numerics;

namespace AtCoderWorkspace
{
    public class Solver
    {
        public void Solve()
        {
            var cin = new Scanner();
            var a = cin.nextInt();
            var b = cin.nextInt();
            var c = cin.nextInt();
            var d = cin.nextInt();

            while (true)
            {
                c -= b;
                if (a <= 0)
                {
                    Console.WriteLine("No");
                    return;
                }
                a -= d;
                if (c <= 0)
                {
                    Console.WriteLine("Yes");
                    return;
                }
            }

        }
    }

    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public int nextInt()
        {
            return int.Parse(next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt() + add;
            }
            return Array;
        }

        public int[] DPArrayInt(int N, int ex)
        {
            int[] Array = new int[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt();
            }
            return Array;
        }

        public long nextLong()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong() + add;
            }
            return Array;
        }

        public long[] DPArrayLong(int N, int ex)
        {
            long[] Array = new long[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong();
            }
            return Array;
        }

        public double nextDouble()
        {
            return double.Parse(next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble() + add;
            }
            return Array;
        }
    }

    class Program
    {
        static void Main(string[] s) => new Solver().Solve();
    }
}


Measured memory_bytes: 27532
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int 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;
int main(){
    ll x,y;
    cin>>x>>y;
    if(abs(x-y)<=1){
        cout<<"Brown"<<endl;
    }else{
        cout<<"Alice"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX_N 101
#define MAX_W 100001
long long dp[MAX_N][MAX_W];
int N;
int W;
int v[MAX_N];
int w[MAX_N];
int function()
{
	for (int i = 0; i < N; i++)
	{
		dp[0][i] = 0;
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j <= W; j++)
		{
			dp[i+1][j] = max(dp[i + 1][j], dp[i][j]);
			if (j + w[i] <= W)
			{
				dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
			}
		}
	}
	return dp[N][W];
}
int main()
{
	
	cin >> N >> W;
	
	for (int i = 0; i < N; i++)
	{
		cin >> v[i] >> w[i];
	}
	cout << function() << endl;
}






Measured memory_bytes: 11320
//#include <ext/pb_ds/assoc_container.hpp> 
 //#include <ext/pb_ds/tree_policy.hpp>
// #include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <iterator>
#include <functional>
#include <limits>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <stack>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define trace(x) cerr << #x << ": " << x << " " << endl;

typedef int64_t ll;
 
#define endl '\n'
#define int ll
ll mod=998244353;
ll mod1=1e9+5;
ll power(ll a,ll b)
{
    if(b==0) return 1;
    else if(b%2==0)
        return power(((((a)%mod)*((a)%mod))%mod),b/2)%mod;
    else return (((a)%mod)*(power(((((a)%mod)*((a)%mod))%mod),b/2)%mod))%mod;
}
inline ll inverse(ll a,ll md) {
  a %= md;
  if (a < 0) a += md;
  ll b = md, u = 0, v = 1;
  while (a) {
    ll t = b / a;
    b -= t * a; swap(a, b);
    u -= t * v; swap(u, v);
  }
  assert(b == 1);
  if (u < 0) u += md;
  return u;
}
  
  
 //using namespace __gnu_pbds;
 //#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
//find_by_order(k)  returns iterator to kth element starting from 0;
//order_of_key(k) returns count of elements strictly smaller than k;
//erase,insert same as normal set
// mt19937 mrand(chrono::high_resolution_clock::now().time_since_epoch().count()); for randomized solution
const int ce=998244353;
ll fast_mod(ll input)
{
    return input < ce ? input : input%ce;
}
#define pi acos(-1)

int32_t main()
{
    IOS

    
    int s,w;
    cin>>s>>w;
    if(w>=s)
    {
        cout<<"unsafe";
    }
    else
        cout<<"safe";
}       


Measured memory_bytes: 3584
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class F { public static void Main() => (new Solver()).Solve(); }

public class Solver
{
	public void Solve()
	{
		long N = GetLong();
		var ls = new List<Tuple<long, long>>();
		var rs = new List<Tuple<long, long>>();
		long total = 0;
		for(long i = 0; i < N; i++)
		{
			var S = GetString();
			long h = 0;
			long b = 0;
			for(int j = 0; j < S.Length; j++)
			{
				if(S[j] == '(')
					h++;
				else
					h--;

				chmin(ref b, h);				
			}
			if(h > 0)
				ls.Add(Tuple.Create(b, h));
			else
				rs.Add(Tuple.Create(b - h, -h));

			total += h;
		}
		Comparison<long> comp = (x, y) => x.CompareTo(y);
		ls.Sort((x, y) => comp(y.Item1, x.Item1));
		rs.Sort((x, y) => comp(y.Item1, x.Item1));
		if(check(ls) && check(rs) && total == 0)
			WriteLine("Yes");
		else
			WriteLine("No");
	}

	private bool check(List<Tuple<long, long>> list)
	{
		long h = 0;
		foreach(var pair in list)
		{
			long b = h + pair.Item1;
			if(b < 0)
				return false;

			h += pair.Item2;
		}
		return true;
	}
}

public static class MyIO
{
	private static string[] args = new string[0];
	private static int cnt = 0;
	private static IEnumerable<string> getArgs(long N) => Range(0, N).Select(_ => getArg());
	private static string getArg()
	{
		if(cnt == args.Length) { args = Console.ReadLine().Split(); cnt = 0; }
		return args[cnt++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static decimal GetDecimal() => decimal.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(long N) => getArgs(N).Select(int.Parse).ToArray();
	public static long[] GetLongs(long N) => getArgs(N).Select(long.Parse).ToArray();
	public static double[] GetDoubles(long N) => getArgs(N).Select(double.Parse).ToArray();
	public static decimal[] GetDecimals(long N) => getArgs(N).Select(decimal.Parse).ToArray();
	public static string[] GetStrings(long N) => getArgs(N).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) < 0) x = y; }
	public static void chmin<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) > 0)	x = y; }
	public static void swap<T>(ref T x, ref T y) { T tmp = x; x = y; y = tmp; }
	public static long rightShift(long x, long y) => (x >> (int)y);
	public static long leftShift(long x, long y) => (x << (int)y);
	public static bool contains(long s, long x) => (rightShift(s, x) & 1L) == 1L;
	public static long gcd(long x, long y) => (y == 0) ? x : gcd(y, x % y);
	public static long lcm(long x, long y) => (x / gcd(x,y)) * y;	
	public static IEnumerable<int> Range(long start, long count) => Enumerable.Range((int)start, (int)count);
	public static void Sort(this List<string> source) => source.Sort(StringComparer.Ordinal);
}


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

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> dp(1000001, 0);
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    for (auto v : a)
    {
        if (dp[v] != 0)
        {
            dp[v] = 2;
            continue;
        }
        for (int i = v; i < 1000001; i += v)
            dp[i]++;
    }

    for (auto v : a)
    {
        if (dp[v] == 1)
            ans++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 7980
from collections import defaultdict


def solve(n, k, a_list):
    b_list = [a - 1 for a in a_list]
    res_dict = defaultdict(list)
    res_dict[0].append(0)

    r = 0
    for i in range(n):
        r += b_list[i]
        r %= k
        res_dict[r].append(i + 1)

    res = 0
    for r in res_dict.keys():
        r_list = res_dict[r]
        if len(r_list) == 1:
            continue
        i = 0
        j = 0
        # print(r_list)
        while i < len(r_list) - 1:
            if j < len(r_list) - 1:
                while r_list[j + 1] - r_list[i] < k:
                    j += 1
                    if j == len(r_list) - 1:
                        break
            res += j - i
            # print(i, j)
            i += 1
    return res


def main():
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))
    res = solve(n, k, a_list)
    print(res)


def test():
    assert solve(5, 4, [1, 4, 2, 3, 5]) == 4
    assert solve(8, 4, [4, 2, 4, 2, 4, 2, 4, 2]) == 7
    assert solve(10, 7, [14, 15, 92, 65, 35, 89, 79, 32, 38, 46]) == 8


if __name__ == "__main__":
    # test()
    main()


Measured memory_bytes: 68216
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

typedef long long ll;
const int N = 200100;
ll a[N], b[N];

int main(){
	int a, b, c;
	int flag = 0;
	while(~scanf("%d %d %d", &a, &b, &c)){
		for(int i = 1; i <= 500; i++){
			int d = b * i + c;
			int e = d / a;
			if(e * a == d){
				flag = 1;
				break;
			}
		}
		if(flag)
			printf("YES\n");
		else
			printf("NO\n");
	}
}

Measured memory_bytes: 384
### inner classes

class BIT
  def initialize(n)
    @n = n
    @bits = (n + 1).times.map{0}
  end

  def sum(x)
    s = 0
    while x > 0
      s += @bits[x]
      x -= (x & -x)
    end
    s
  end

  def add(x, v)
    while x <= @n
      @bits[x] += v
      x += (x & -x)
    end
  end
end

class BIT2D
  def initialize(m, n)
    @m = m
    @bits = (m + 1).times.map{BIT.new(n)}
  end

  def sum(y, x)
    s = 0
    while y > 0
      s += @bits[y].sum(x)
      y -= (y & -y)
    end
    s
  end

  def add(y, x, v)
    while y <= @m
      @bits[y].add(x, v)
      y += (y & -y)
    end
  end
end

### main

m, n = gets.strip.split(' ').map{|s| s.to_i}
k = gets.strip.to_i

bit2ds = {}
bit2ds['J'] = BIT2D.new(m, n)
bit2ds['O'] = BIT2D.new(m, n)
bit2ds['I'] = BIT2D.new(m, n)

for y in (1..m)
  hl = gets.strip.split('')

  for x in (1..n)
    bit2ds[hl[x - 1]].add(y, x, 1)
  end
end

k.times do
  a, b, c, d = gets.strip.split(' ').map{|s| s.to_i}
  sums = []

  for ch in ['J', 'O', 'I']
    b2d = bit2ds[ch]
    sum =
      b2d.sum(c, d) - b2d.sum(a - 1, d) -
      b2d.sum(c, b - 1) + b2d.sum(a - 1, b - 1)

    sums << sum
  end

  puts sums.join(' ')
end

Measured memory_bytes: 41208
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(ll i = 0; i < n; i++)
const ll INF = 1LL << 60;

int main(){
    int H, W; cin >> H >> W;
    int sx, sy, gx, gy; cin >> sx >> sy >> gx >> gy;
    sx--;sy--;gx--;gy--;
    vector<vector<int>> G(H, vector<int>(W, 0));
    vector<vector<int>> Group(H, vector<int>(W, -1));
    rep(i, H)rep(j, W){
        char c; cin >> c;
        if(c == '#')G[i][j] = 1;
    }

    int tag = 0;
    
    rep(i, H){
        rep(j, W){
            if(G[i][j] == 1)continue;
            if(Group[i][j] != -1)continue;
            queue<pair<int, int>> que;
            que.push(make_pair(i, j));
            while(!que.empty()){
                pair<int, int> p = que.front(); que.pop();
                if(Group[p.first][p.second] != -1) continue;
                Group[p.first][p.second] = tag;
                if(p.first - 1 >= 0){
                    if(G[p.first - 1][p.second] == 0) que.push(make_pair(p.first - 1, p.second));
                }
                if(p.first + 1 < H){
                    if(G[p.first + 1][p.second] == 0) que.push(make_pair(p.first + 1, p.second));
                }
                if(p.second - 1 >= 0){
                    if(G[p.first][p.second - 1] == 0) que.push(make_pair(p.first, p.second - 1));
                }
                if(p.second + 1 < W){
                    if(G[p.first][p.second + 1] == 0) que.push(make_pair(p.first, p.second + 1));
                }
            }
            tag++;
        }
    }
    
    // rep(i, H){
    //     rep(j, W)cout << Group[i][j];
    //     cout<<endl;
    // }

    set<pair<int, int>> ans;
    rep(i, H){
        rep(j, W){
            if(G[i][j] == 1)continue;
            //左上方向
            int dh[] = {-2, -1, 0, 1, 2};
            int dw[] = {-2, -1, 0, 1, 2};
            rep(n, 5){
                rep(m, 5){
                    if(i + dh[n] >= 0 && i + dh[n] < H && j + dw[m] >= 0 && j + dw[m] < W){
                        if(Group[i][j] != Group[i + dh[n]][j + dw[m]] && Group[i + dh[n]][j + dw[m]] != -1){
                            ans.insert(make_pair(Group[i][j], Group[i + dh[n]][j + dw[m]]));
                        }
                    }
                }
            }
        }
    }
    Graph ansG(tag);
    for(auto x:ans){
        ansG[x.first].push_back(x.second);
    }
    

    queue<int> que;
    que.push(Group[sx][sy]);
    int goalGroup = Group[gx][gy];
    vector<int> dist(tag, -1);
    dist[Group[sx][sy]] = 0;
    while(!que.empty()){
        int v = que.front(); que.pop();
        for(auto x:ansG[v]){
            if(dist[x] != -1)continue;
            dist[x] = dist[v] + 1;
            que.push(x);
        }
    }
    cout << dist[goalGroup] << endl;
    // rep(i, tag){
    //     rep(j, ansG[i].size())cout << ansG[i][j]<<" ";
    //     cout << endl;
    // }
}


Measured memory_bytes: 37052
#!/usr/bin/env python3
n, m = map(int, input().split())
*h, = map(int, input().split())
h = [0] + h
i = [0] + [1] * n

for j in range(m):
    a, b = map(int, input().split())
    if h[a] >= h[b]:
        i[b] = 0
    if h[a] <= h[b]:
        i[a] = 0
print(sum(i))

Measured memory_bytes: 20032
#include <random>

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld eps = 1e-12;
constexpr int inf = numeric_limits<int>::max() / 2;
constexpr ll mod = 1e9 + 7;
mt19937_64 rnd{random_device()()};

template <typename T>
void printv(const vector<T> &v) {
  int sz = v.size();
  for (int i = 0; i < sz; i++) {
    cout << v[i] << " \n"[i == sz - 1];
  }
}

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

  int n;
  cin >> n;
  vector<ll> a(n);
  ll odd = 0, even = 0, ma = -inf;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    ma = max(ma, a[i]);
    if (a[i] <= 0) {
      continue;
    }
    if (i % 2) {
      odd += a[i];
    } else {
      even += a[i];
    }
  }
  vector<int> need(n);
  if (ma <= 0) {
    cout << ma << endl;
    for (int i = 0; i < n; i++) {
      if (a[i] == ma) {
        need[i] = 1;
        break;
      }
    }
  } else {
    cout << max(odd, even) << endl;
    if (odd <= even) {
      for (int i = 0; i < n; i++) {
        if (i % 2) continue;
        if (a[i] <= 0) continue;
        need[i] = 1;
      }
    } else {
      for (int i = 0; i < n; i++) {
        if (i % 2 == 0) continue;
        if (a[i] <= 0) continue;
        need[i] = 1;
      }
    }
    vector<int> needs;
  }
  vector<int> ans;
  auto add = [&](int pos) {
    cerr << "pos:" << pos << endl;
    ans.push_back(pos + 1);
    vector<int> nxt;
    int sz = need.size();
    if (pos == 0) {
      for (int i = 1; i < sz; i++) nxt.push_back(need[i]);
    } else if (pos == sz - 1) {
      for (int i = 0; i < sz - 1; i++) nxt.push_back(need[i]);
    } else {
      assert(need[pos - 1] == need[pos + 1]);
      for (int i = 0; i < pos - 1; i++) nxt.push_back(need[i]);
      nxt.push_back(need[pos - 1]);
      for (int i = pos + 2; i < sz; i++) nxt.push_back(need[i]);
    }
    need = nxt;
  };
  while (true) {
    bool update = false;
    int sz = need.size();
    assert(sz > 0);
    if (need[0] == 0) {
      add(0);
      continue;
    }
    if (need[sz - 1] == 0) {
      add(sz - 1);
      continue;
    }
    for (int i = 1; i + 1 < sz; i++) {
      if (need[i - 1] == 1 && need[i] == 0 && need[i + 1] == 1) {
        add(i);
        update = true;
        break;
      }
      if (need[i - 1] == 0 && need[i] == 0 && need[i + 1] == 0) {
        add(i);
        update = true;
        break;
      }
    }
    if (!update) {
      break;
    }
  }
  cout << ans.size() << endl;
  for (auto v : ans) cout << v << endl;
}


Measured memory_bytes: 3632
n, m, c = map(int, input().split())
bm = list(map(int, input().split()))
anm = []
for _ in range(n):
    anm.append(list(map(int, input().split())))
    
count = 0
for i in range(n):
    sumAB = 0
    for j in range(m):
        sumAB += anm[i][j] * bm[j]

    #print(sumAB)
    if (sumAB + c) > 0:
        count += 1
print(count)

Measured memory_bytes: 3064
#pragma comment(linker,"/STACK:102400000,102400000")
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <numeric>
#include <queue>
#include <iomanip>
#include <vector>
#include <ctime>
#include <map>
#include <cmath>
const int N = 100010;
#define demid int mid = l + r >> 1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define INF 0x3f3f3f3f
const double eps = 1e-6;
typedef long long ll;
using namespace std;

int main()  
{
  //freopen("in.txt","r",stdin);
  // ios::sync_with_stdio(0);
  	int q;
  	while(~scanf("%d",&q))
  	{
  		ll sum = 0;
  		while(q--)
  		{
  			int loc,cnt,c;char ch;
  			scanf("%d %c %d",&loc,&ch,&cnt);
  			c = (ch == '(')?1:-1;
  			//printf("%d %c %d\n",loc,ch,cnt);
  			sum += c*cnt;
  			if(sum == 0)puts("Yes");
  			else puts("No");
  		}
  	}
    return 0;
}

Measured memory_bytes: 1168
#include <iostream>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 4e5 + 10;
long long a[maxn];
long long pow_mod(long a, long n) {
    long long ret = 1;
    while (n) {
        if (n & 1) ret = ret * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ret;
}

void init() {
    a[0] = 1;
    for (int i = 1; i < maxn; i++) {
        a[i] = a[i - 1] * i % mod;
    }
}

long long Cc(long long x, long long y) {
    return a[x] * pow_mod(a[y] * a[x - y] % mod, mod - 2) % mod;
}

int main() {
    init();
    long long n, k, ans;
    cin >> n >> k;

    ans = Cc(2 * n - 1, n);
    for (int i = 1; i <= n - k - 1; i++) ans = (ans - Cc(n, i) * Cc(n - 1, i - 1) % mod) % mod;
    cout << (ans % mod + mod) % mod << endl;
}

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

ll dp[56][56][2506];

int main(){

  int n,a;
  int x[56];
  int i,j,k,s;
  int sum = 0;
  ll ans = 0;

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

  for(j = 0;j <= 50;j++){
    for(k = 0;k <= 50;k++){
      for(s = 0;s <= 2500;s++) dp[j][k][s] = 0;
    }
  }

  for(i = 0;i <= n;i++) dp[i][0][0] = 1;
  for(j = 1;j <= n;j++){
    for(k = 1;k <= j;k++){
      for(s = 1;s <= sum;s++){
        if(s < x[j]) dp[j][k][s] = dp[j - 1][k][s];

        else {
          dp[j][k][s] = dp[j - 1][k - 1][s - x[j]] + dp[j - 1][k][s];
        }
      }
    }
  }

  for(i = 1;i <= n;i++){
    ans += dp[n][i][i*a];
  }

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

  return 0;
}


Measured memory_bytes: 57600
a = "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ"

t = int(input())
a_str = str(input())
answer = ""

a_uniquie = ''.join(set(a_str))

for i in a_str:
  for j in range(26):
    if i == a[j]:
      answer += a[j+t]
      break

print(answer)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
typedef long long ll;
typedef vector<ll> vl;
#define rp(i, f, t) for (int i = f; i < t; i++)
#define pr(i, f, t) for (int i = t - 1; i >= f; i--)
#define ca(n, a) rp(ca_i, 0, n) cout << a[ca_i] << ((ca_i == n - 1) ? "\n" : " ")
#define za(n, a) rp(za_i, 0, n) a[za_i] = 0
#define be(a) a.begin(), a.end()
int main()
{
	ll n;
	cin>>n;
	ll a[n];
	rp(i,0,n)cin>>a[i];
	bool sig=true;
	map<ll,ll> mp;
	rp(i,0,n)mp[a[i]]++;
	for(auto i=mp.begin();i!=mp.end();i++){
		if(i->second>=2)
		{
			sig=false;
		}
	}
	if(sig)
	cout<<"YES"<<endl;
	else
	cout<<"NO"<<endl;
}


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

int block;

void solve(int x,int y,int h,int w,char data[h][w],int path){
	//printf("%d\n",path);
	if((x+1==h-1 && y==w-1) || (x==h-1 && y+1==w-1)){
		if(block==path+2){
		printf("Possible\n");
		return;
		}
		printf("Impossible\n");
		return;
	}
	if(data[x+1][y]=='#')solve(x+1,y,h,w,data,path+1);
	else if(data[x][y+1]=='#')solve(x,y+1,h,w,data,path+1);
	else{
		printf("Impossible\n");
		return;
	}

	return;
}

int main(){
	int h,w;
	scanf("%d %d",&h,&w);
	char data[h][w];
	for(int i=0; i<h; i++){
		scanf("%s",&data[i]);
		for(int j=0; j<w; j++){
			if(data[i][j]=='#')block++;
		}
	}

	solve(0,0,h,w,data,0);

	return 0;
}


Measured memory_bytes: 128