akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>


using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define clear(arr, val) memset(arr, val, sizeof(arr))

#define rep(i, n) for (int i = 0; i < n; ++i)

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

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

const double EPS = 1e-8;
const double PI = acos(-1.0);
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };


const int MAX = 1000000;
int cal(int n) { return n*(n+1)*(n+2)/6; }
void dpru(int* res, const vector<int>& tet)
{
	static bool dp[MAX + 1];
	clear(dp, 0);
	dp[0] = true;
	for (int i = 1, num = 0; num < MAX; ++i)
	{
		for (int j = MAX; j >= 0; --j)
		{
			if (!dp[j])
			{
				for (int k = 0; !dp[j] && k < tet.size() && j - tet[k] >= 0; ++k)
					dp[j] = dp[j - tet[k]];
				if (dp[j])
				{
					res[j] = i;
					++num;
				}
			}
		}
	}
}
int main()
{
	vector<int> tetra, odd_tetra;
	for (int i = 1; cal(i) <= MAX; ++i)
	{
		tetra.push_back(cal(i));
		if (cal(i) & 1)
			odd_tetra.push_back(cal(i));
	}

	static int min_tet[MAX + 1], min_odd_tet[MAX + 1];
	dpru(min_tet, tetra);
	dpru(min_odd_tet, odd_tetra);

	int n;
	while (scanf("%d", &n), n)
		printf("%d %d\n", min_tet[n], min_odd_tet[n]);
}

Measured memory_bytes: 0
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(ll i = (ll)(s); i < (ll)(t); i++)
#define rrep(i,s,t) for(ll i = (ll)(s-1);(ll)(t) <= i; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
constexpr ll INF = numeric_limits<ll>::max()/4;
constexpr ll n_max = 2e5+10;
#define int ll
const long double pi = 3.14159265358979323846;

template <typename A, typename B>
string to_string(pair<A, B> p);
string to_string(const string &s) {return '"' + s + '"';}
string to_string(const char *c) {return to_string((string) c);}
string to_string(bool b) {return (b ? "true" : "false");}
template <size_t N>
string to_string(bitset<N> v){
    string res = "";
    for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]);
    return res;
}
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) res += ", ";
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p){return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}

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

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

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

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n; cin >> n;
    n *= 2;
    if (n == 1) {
        cout << 1 << "\n";
        return 0;
    }
    vector<ll> pri;
    ll n2 = n;
    for (ll i = 2; i * i <= n2; i++) {
        if(n2 % i == 0){
            ll tmp = 1;
            while(n2 % i == 0){
                tmp *= i;
                n2 /= i;
            }
            pri.emplace_back(tmp);
        }
    }
    if(n2 > 1)pri.emplace_back(n2);
    debug(pri);
    ll m = pri.size();
    ll ans = INF;

    rep(i,0,(1LL << m)){
        ll a = 1;
        rep(j,0,m){
            if((i >> j) & 1){
                a *= pri[j];
            }
        }
        ll b = n / a;
        debug(a, b);
        if(a == 1 || b == 1){
            chmin(ans, n - 1);
            continue;
        }
        ll x = modinv(b, a);
        debug(x);
        chmin(ans, b * x - 1);
        x = modinv(a, b);
        debug(x);
        chmin(ans, a * x - 1);
    }

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

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m,l; cin>>n>>m>>l;
    int a[n][m];
    int b[m][l];
    for ( int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            int v; cin>>v;
            a[i][j]=v;
        }
    }
    for(int i=0; i<m; i++){
        for(int j=0; j<l; j++ ){
            int w; cin>>w;
            b[i][j]=w;
        }
    }

    long long ans[n][l];
    for (int i=0; i<n; i++){
        for(int j=0; j<l; j++){
            ans[i][j]=0;
            for(int k=0; k<m; k++){
                ans[i][j]+=a[i][k]*b[k][j];
            }
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<l; j++){
            if(j==l-1) cout<<ans[i][j]<<endl;
            else cout<<ans[i][j]<<' ';
        }
    }
    return 0;
}


Measured memory_bytes: 3328
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
int main() {
    ll x, y; cin >> x >> y;
    int cnt = 1;
    while (x <= y) {
        x = 2 * x;
        cnt++;
    }
    cout << cnt - 1 << endl;
    
}




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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin>>s;
    for(int i = 0; i < s.size(); i++)
    {
        cout<<"x";
    }    
    return 0;
    
}

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

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef long long ll;
typedef long double ld;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define fi first
#define se second

template<class T> bool ckmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<class T> bool ckmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}

const int MX = 3020;
const ll INF = 1e18;

ll dp[MX][MX][4];
int vred[MX][MX];

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

    int r, c, ku;
    cin >> r >> c >> ku;

    for(int i = 0; i < ku; ++i)
    {
        int a, b, v;
        cin >> a >> b >> v;
        --a, --b;
        vred[a][b] = v;
    }

    for(int i = 0; i < r; ++i)
    {
        for(int j = 0; j < c; ++j)
        {
            for(int k = 0; k < 4; ++k)
            {
                dp[i][j][k] = -INF;
            }
        }
    }

    dp[0][0][0] = 0;

    for(int i = 0; i < r; ++i)
    {
        for(int j = 0; j < c; ++j)
        {
            for(int k = 2; ~k; --k)
            {
                if(dp[i][j][k] != -INF)
                {
                    ckmax(dp[i][j][k+1], dp[i][j][k] + vred[i][j]);
                }
            }

            for(int k = 0; k <= 3; ++k)
            {
                //cout << "alo" << endl;
                if(dp[i][j][k] != -INF)
                {
                    if(i + 1 < r)
                    {
                        ckmax(dp[i+1][j][0], dp[i][j][k]);
                    }
                    if(j + 1 < c)
                    {
                        ckmax(dp[i][j+1][k], dp[i][j][k]);
                    }
                }
            }
        }
    }


    ll ans = -INF;

    for(int k = 0; k < 4; ++k)
        ckmax(ans, dp[r-1][c-1][k]);
    cout << ans << "\n";
}


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

#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 trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pii> vii;

const int N = 212345;
ll n;
vi c(N);
vl dp(N), ans(N), cov(N);
vvi g(N);

void dfs(int u=1, int p=1) {
  trav(v, g[u]) if (v!=p) {
    dfs(v,u);
    dp[u] += dp[v]+1;
  }
}

void dfs1(int u=1, int p=1) {
  ll b4 = cov[c[u]];
  trav(v, g[u]) if (v!=p) {
    ll a = cov[c[u]];
    dfs1(v,u);
    ll b = cov[c[u]];
    ll opt = dp[v]+1-(b-a);
    ans[c[u]] -= opt*(opt-1)/2;
  }
  cov[c[u]] = b4+dp[u]+1;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);

  cin >> n;
  fill(all(ans), n*(n-1)/2);

  rep(i,1,n+1) cin >> c[i];
  rep(i,0,n-1) {
    int a, b;
    cin >> a >> b;
    g[a].pb(b);
    g[b].pb(a);
  }

  dfs();
  dfs1();

  rep(i,1,n+1) ans[i] -= (n-cov[i])*(n-cov[i]-1)/2;
  rep(i,1,n+1) ++ans[c[i]];
  rep(i,1,n+1) cout << ans[i] << '\n';

}

Measured memory_bytes: 35928
from collections import deque

class Graph(): #directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.rev = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append(e[1] - indexed)
            self.rev[e[1] - indexed].append(e[0] - indexed)
            self.deg[e[1] - indexed] += 1

    def topological_sort(self):
        deg = self.deg[:]
        res = [i for i in range(self.n) if deg[i] == 0]
        queue = deque(res)
        used = [False for _ in range(self.n)]
        while queue:
            node = queue.popleft()
            for adj in self.graph[node]:
                deg[adj] -= 1
                if deg[adj] == 0:
                    queue.append(adj)
                    res.append(adj)
        return res

N, M = map(int, input().split())
E = [tuple(map(int, input().split())) for _ in range(N + M - 1)]

g = Graph(N, E)
ts = g.topological_sort()
node_to_ts = [0 for _ in range(N)]

for i in range(N):
    node_to_ts[ts[i]] = i

for i in range(N):
    tmp = -1
    res = -1
    for j in g.rev[i]:
        if tmp < node_to_ts[j]:
            tmp = node_to_ts[j]
            res = j
    print(res + 1)

Measured memory_bytes: 93656
// 復習

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

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

    int n; cin >> n;
    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, a+n);
    sort(c, c+n);

    ll res = 0;
    for (int i = 0; i < n; ++i) {
        int* posA = lower_bound(a, a+n, b[i]);
        ll top = distance(a, posA);
        int* posC = upper_bound(c, c+n, b[i]);
        ll bottom = distance(posC, c+n);
        res += top * bottom;
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1408
/**
 *    Author:  "Robin Singh" !!!!    
**/
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
#define mp make_pair
#define str string 
#define szz(v) ((int)(v).size())  
#define fr(i, j, k) for(int i = j; i < k; i++)     // 0 -> n-1 (i,0,n)
#define bk(i, j, k) for(int i = j-1; i >= k; i--)  // n-1 -> 0 (i,n,0)
#define frit(it, a) for(__typeof((a).begin()) it = a.begin(); it != a.end(); ++it)
#define mem(ptr)  memset(ptr, 0, sizeof ptr)  // use fill() for value other than 0 //
#define rtn return 
#define itt(a)   __typeof((a).begin())
#define RT  (cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n")  // Run Time
#define nl "\n"  // New Line
#define dbg(x) (cerr << #x << " = " << x << "  ")
#define enl (cerr << "\n")
#define dbgg(x,y) (cerr << #x << " = " << x << " -> " << #y << " = " << y << "\n")
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector< pair<int,int> > vpii;
typedef vector< pair<ll, ll> > vpll;
const long long mod = 1e9+7;
const ld eps = 1e-9;
const int inf = (1<<30);
const ll INF = (1LL<<61);

ll gcd(ll a,ll b) { return b==0 ? a : gcd(b, a%b); }
ll expo(ll x, ll y){ ll res = 1; x = x % mod;  while (y > 0) { if (y & 1)res = (res*x) % mod; y = y>>1;x = (x*x) % mod;}return res;}
void matmul(ll a[][2], ll b[][2]) { ll tmp[2][2]; for(int i=0; i<2; i++) { for(int j=0; j<2; j++) { tmp[i][j] = 0; for(int k=0; k<2; k++) tmp[i][j] = (tmp[i][j] + a[i][k]*b[k][j]) % mod; }} for(int i=0; i<2; i++) for(int j=0; j<2; j++) a[i][j] = tmp[i][j]; }  // answer stored in matrix A
ll fibo(int n)    // returns nth fibonacci number, also S(n) = f(n+2)-1
{ if(n == 0) return 0; else if(n == 1) return 1; ll T[2][2] = { {0, 1} , {1, 1} }; ll res[2][2] = { {1, 0}, {0,1} }; n--; while(n) { if(n & 1) matmul(res, T); n >>= 1; matmul(T, T); } return res[1][1]; }
ll ainv, binv;
void extgcd(ll a, ll b){ if(b==0){/* hcf = a; */ ainv = 1; binv = 0; } else{ extgcd(b, a%b); ll temp = ainv; ainv = binv; binv = temp - (a/b)*binv; } }

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    str s;
    cin >> s;
    int n = szz(s), c = 0;
    if(s[0] != 'A'){
        cout << "WA";
        rtn 0;
    }
    fr(i, 0, n){
        if(s[i] != 'A' && s[i] != 'C'){
            if(s[i] >= 'a' && s[i] <= 'z') continue;
            else{
                cout << "WA";
                rtn 0;
            }
        }
        if(s[i] == 'C' && i>=2 && i <= n-2) c++;
    }
    if(c == 1) cout << "AC";
    else cout << "WA";
    return 0; 
}

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

const int N = 3e5 + 10;
int n, W[N], E[N], ans = N;
char s[N];

int main() {
    cin >> n;
    cin >> (s + 1);
    for (int i = 1; i <= n; i++) {
        W[i] = W[i - 1], E[i] = E[i - 1];
        if (s[i] == 'W') W[i]++;
        else E[i]++;
    }
    for (int i = 1; i <= n; i++) {
        int t = W[i - 1] + E[n] - E[i];
        ans = min(ans, t);
        // cout << ans << endl;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
void print() { cout << "\n"; }
template <class T> void print(const T &x) { cout << x << "\n"; }
template <class T, class... Args> void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
template <class T> void printVector(const vector<T> &v) {
    for(const T &x : v) {
        cout << x << " ";
    }
    cout << "\n";
}
using ll = long long;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
constexpr int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    if(n & 1) {
        for(int l = 1, r = n - 1; l < r; l++, r--) {
            if(m <= 0) {
                break;
            }
            print(l, r);
            m--;
        }
    } else {
        bool f = true;
        for(int l = 1, r = n - 1; l < r; l++, r--) {
            if(m <= 0) {
                break;
            }
            if(r - l <= n / 2 && f) {
                r--;
                f = false;
            }
            print(l, r);
            m--;
        }
    }
}

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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

int main() {
  int N, L;
  cin >> N >> L;
  vector<string> s(N);
  rep(i, N) cin >> s.at(i);
  sort(s.begin(), s.end());
  rep(i, N) {
    cout << s.at(i);
  }
  cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1001001001
#define LINF 1001001001001001001
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

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

int main() {

    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    rep(i,N) {
        cin >> A[i];
        A[i]--;
        A[i] %= K;
    }
    vector<ll> S(N + 1);
    S[0] = 0;
    rep(i,N) S[i + 1] = (S[i] + A[i]) % K;

    map<int, int> m;

    ll ans = 0;
    for (int i = 0; i <= N; i++) {
        if (i >= K) {
            m[S[i - K]]--;
            if (m[S[i - K]] == 0) m.erase(S[i - K]);
        }
        if (m.find(S[i]) == m.end()) m.emplace(S[i], 1);
        else {
            ans += m[S[i]];
            m[S[i]]++;
        }
    }

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

Measured memory_bytes: 14832
#include <bits/stdc++.h>
#define rep(i,n) for(long long i=0; i<n; i++)
#define Rep(i,n) for(long long i=1; i<n; i++)
#define ll long long
#include <math.h>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <vector>


using namespace std;
#define PI acos(-1)
using P =pair<ll,ll>;

ll ketasu(ll a){
   ll num=1;
   while(a/10){
       num++;
       a/=10;
   }
   return num;
}

ll gcd(ll a,ll b){return b ? gcd(b,a%b) :a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

ll kosuu(ll a){
    ll sum=0;
    for(ll i=1;i*i<=a;i++){
        if(a%i==0){
            if(a!=1&&i*i!=a){
            sum+=2;
            }else{
             sum++;   
            }
        }
    }
    return sum;
}

ll n;



    vector<pair<ll,ll>>p;
void fs(ll a){
    for(ll i=2;i*i<=n;i++){
        ll cnt=0;
        while(n%i==0){
            n/=i;
            cnt++;
        }
        p.emplace_back(i,cnt);
    }
    return;
}


ll di[]={1,0,-1,0};
ll dj[]={0,-1,0,1};
int main(){
   int n;
   cin>>n;
    long long int a[n],ans=0,i;
    int mod=1000000007;
    long long int sum=0;
 
    for( i = 0 ; i < n ; i++ ){
            cin>>a[i];
        sum = sum + a[i];
    }
    for( i = 0 ; i < n ; i++ ){
        sum = sum - a[i];
 
        ans+=(a[i]%mod * (sum%mod))%mod;
        ans%=mod;
    }
    cout<<ans%mod;
 
    return 0;
}
 




Measured memory_bytes: 5196
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<(n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;
struct Grid{ll x,y,t;};
struct Edge{ll to,cost;};
struct Graph{vector<vector<Edge>>E;int V;
  const ll Inf = llINF;const int MAX_V=201010;vector<ll>d;
  Graph(int n):E(n){d.resize(MAX_V);E.resize(n);V=n;}
  void init(){for(int i=0;i<MAX_V;i++)d[i]=Inf;}
  void add_edge(ll from,ll to,ll cost){E[from].pb({to,cost});}
};
ll kake[1000][1000];
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll h,w;cin>>h>>w;
  ll ans=0;
  for(int i=0;i<h/2+(h%2);i++){
    for(int j=0;j<w/2+(w%2);j++){
      kake[i][j]=(h-i)*(i+1)*(w-j)*(j+1);
      if(h%2==1&&i==h/2*(h%2) && w%2==1&&j==w/2*(w%2)){
      }else if(h%2==1&&i==h/2*(h%2)){
	kake[i][w-j-1]=(h-i)*(i+1)*(w-j)*(j+1);
      }else if(w%2==1&&j==w/2*(w%2)){
	kake[h-i-1][j]=(h-i)*(i+1)*(w-j)*(j+1);
      }else{
	kake[h-i-1][j]=(h-i)*(i+1)*(w-j)*(j+1);
	kake[h-i-1][w-j-1]=(h-i)*(i+1)*(w-j)*(j+1);
	kake[i][w-j-1]=(h-i)*(i+1)*(w-j)*(j+1);
      }
    }
  }

  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      ll num;
      cin>>num;
      ans+=num*kake[i][j];
    }
  }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 7136
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define MOD 1000000007
#define PI acos(-1)
#define eps (1e-8)
#define INF ((int)1e18)
//ifstream cinn("in.in");ofstream coutt("out.out");


signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    string s;cin>>s;
    int sum=0;
    for(char c:s){
        sum=(sum+(c-'0'))%9;
    }
    if(sum%9==0)cout<<"Yes";
    else cout<<"No";
}

Measured memory_bytes: 3768
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	s := []string{next(), next(), next()}
	// index
	c := []int{0, 0, 0}

	p := 0
	var nextp int
	for c[p] < len(s[p]) {
		nextp = int(s[p][c[p]] - 'a')
		c[p]++
		p = nextp
	}
	puts(string('A' + p))
}

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}


Measured memory_bytes: 640
#include<stdio.h>
int main(void)
{
	int n,a,b,c,i;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d %d %d",&a,&b,&c);
		if(a*a==b*b+c*c){
			printf("YES\n");
		}
		else if(b*b==a*a+c*c){
			printf("YES\n");
		}
		else if(c*c==a*a+b*b){
			printf("YES\n");
		}
		else{
			printf("NO\n");
		}
	}
	return 0;
}


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

int main(){
    
    cin.tie(0);
    ios::sync_with_stdio(false);
   
    int n;
    cin >> n;
    
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    
    vector<int> vec(100001);
    
    rep(i,n){
        if(a[i]!=0) vec[a[i]-1]++;
        vec[a[i]]++;
        vec[a[i]+1]++;
    }
    
    int maxv = *max_element(vec.begin(), vec.end());
    
    cout << maxv << endl;

}

Measured memory_bytes: 1024
n = gets.to_i
taro = 0
hanako = 0

for j in 1..n

s, t =  gets.split

if (s<t) == true then
hanako += 3
else
if (s>t) == true then
taro += 3
else
hanako += 1
taro += 1
end
end

end

puts "#{taro} #{hanako}"



Measured memory_bytes: 6852
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,max=1;
    cin>>a;
    for(int i=2;i*i<=a;i++){
            int j=i;
        while(j<=a){
            if(j*i>a) break;
            j=j*i;
        }
        if(max<j) max=j;
    }
    cout<<max<<endl;
}


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

#define REP( i, n )     for( int (i) = 0; (i) < (n); (i)++ )
#define ALL( a )        (a).begin(), (a).end()

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

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

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;

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

    bool flag = false;
    REP( i, s.size() - 1 ){
        if( s[i] != s[i + 1] ) flag = true;
    }

    if( !flag && s.size() % 2 == 1 ){
        cout << s.size() * K / 2 << endl;
    }else if( s.size() == 1 ){
        cout << K / 2 << endl;
    }else{
        ll ans = 0;

        if( s[0] == s[s.size() - 1] ){
            int front = 1, back = 1;
            int i = 0;
            while( i < s.size() - 1 && s[i] == s[i + 1] ){
                front++;
                i++;
            }
            
            i = s.size() - 1;
            while( i >= 1 && s[i - 1] == s[i] ){
                back++;
                i--;
            }
            if( !( ( front + back ) % 2 == 1 && front % 2 == 0 ) ){
                ans += K - 1;
            }
            
        }


        ll t = 0, t2 = 0;
        REP( i, s.size() - 1 ){
            while( i < s.size() - 1 && s[i] == s[i + 1] ){
                t++;
                i++;
            }
            t2 += ( t + 1 ) / 2;
            t = 0;
        }

        if( s[0] != s[s.size() - 1] ){
            ans += t2 * K;
        }else{

            ans += t2;

            t = 0, t2 = 0;
            REP( i, s.size() - 2 ){
                while( i < s.size() - 2 && s[i] == s[i + 1] ){
                    t++;
                    i++;
                }
                t2 += ( t + 1 ) / 2;
                t = 0;
            }

            ans += t2 * ( K - 1 );
        }

        cout << ans << endl;
    }
}


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

using ll = long long;

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

	ll a, b, c, k;
	cin >> a >> b >> c >> k;


	ll ones = min(k, a);
	ll zeros = min((k - ones), b);  
	ll minos = (k - ones - zeros);

	ll ans = (1 * ones) + (-1 * minos);
	cout << ans << endl;

}

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

#define MAX_V 15

typedef pair<int, int> Point;

double dist( const Point& p1, const Point& p2 )
{
	return sqrt( pow( p1.first - p2.first, 2.0 ) + pow( p1.second - p2.second, 2.0 ) );
}

double bitonic_tsp_distance( const vector<Point>& p )
{
	const int N = p.size();
	vector< vector<double> > L( N, vector<double>(N, 0.0) );

	for( int j = 1; j < N; j++ ) {
		for( int i = 0; i < j; i++ ) {
			if( i == 0 && j == 1 ) {
				L[i][j] = dist( p[i], p[j] );
			}
			else if( i < j - 1 ) {
				L[i][j] = L[i][j - 1] + dist( p[j - 1], p[j] );
			}
			else {
				L[i][j] = numeric_limits<double>::infinity();
				for( int k = 0; k < i; k++ ) {
					L[i][j] = min( L[i][j], L[k][i] + dist( p[k], p[j] ) );
				}
			}
		}
	}

	double ans = numeric_limits<double>::infinity();

	for( int k = 0; k < N - 1; k++ ) {
		ans = min( ans, L[k][N - 1] + dist( p[k], p[N - 1] ) );
	}

	return ans;
}

int main()
{
	int n;
	int x, y;
	vector< pair<int, int> > points;

	cin >> n;
	for( int i = 0; i < n; i++ ) {
		cin >> x >> y;
		points.push_back( make_pair( x, y ) );
	}

	cout << fixed << setprecision(8) << bitonic_tsp_distance( points ) << endl;

	return 0;
}



Measured memory_bytes: 10812
n=int(input())
a=list(map(int,input().split()))

def sig(v):
    if v >0:
        return "+"
    elif v<0:
        return "-"
    else:
        return "0"

c_total_sig="+"
c_total=0
cost1=0

for i in range(n):
    temp_total=c_total+a[i]
    temp_total_sig=sig(temp_total)
    #print(i,c_total,temp_total)
    plus=a[i]
    if c_total_sig==temp_total_sig:
        #print(i,c_total,temp_total)
        dif=abs(temp_total)+1
        cost1+=dif
        if temp_total_sig=="-":
            plus=a[i]+dif
        elif temp_total_sig=="+":
            plus=a[i]-dif
    if temp_total_sig=="0" and c_total_sig=="-":
        dif=abs(temp_total)+1
        cost1+=dif
        plus=a[i]+dif
    elif temp_total_sig=="0" and c_total_sig=="+":
        dif=abs(temp_total)+1
        cost1+=dif
        plus=a[i]-dif
    c_total+=plus
    c_total_sig=sig(c_total)

c_total_sig="-"
c_total=0
cost2=0
#print("---------------")
for i in range(n):
    temp_total=c_total+a[i]
    temp_total_sig=sig(temp_total)
    #print(i,c_total,temp_total)
    plus=a[i]
    if c_total_sig==temp_total_sig:
        #print(i,c_total,temp_total)
        dif=abs(temp_total)+1
        cost2+=dif
        if temp_total_sig=="-":
            plus=a[i]+dif
        elif temp_total_sig=="+":
            plus=a[i]-dif
    if temp_total_sig=="0" and c_total_sig=="-":
        dif=abs(temp_total)+1
        cost2+=dif
        plus=a[i]+dif
    elif temp_total_sig=="0" and c_total_sig=="+":
        dif=abs(temp_total)+1
        cost2+=dif
        plus=a[i]-dif
    c_total+=plus
    c_total_sig=sig(c_total)
print(min(cost1,cost2))

Measured memory_bytes: 14332
n,d=map(int,input().split())
l=[[] for i in range(n)]
for i in range(n):
  l[i]=list(map(int,input().split()))
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    c=0
    for h in range(d):
      c+=(l[i][h]-l[j][h])**2
    if (int(c**(1/2)))**2==c:
      ans+=1
print(ans)


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

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll ;
typedef long double ld ;

const ll MOD = 1e9 + 7, N = 1e6 + 5 ;
const double PI = 2 * acos(0.0) ;
const long double EPS = 1.0E-14 ;

vector <ll> R, G, B ;


int main()
{
    ll n, rFlag = 0, gFlag = 0, bFlag = 0, dist, newDist, ans = 0, rCheck = 0, gCheck = 0, bCheck = 0 ;
    string s ;
    cin >> n >> s ;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R')    R.push_back(i) ;
        else if (s[i] == 'G')   G.push_back(i) ;
        else if (s[i] == 'B')   B.push_back(i) ;
    }
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R')    rFlag = 1 ;
        if (s[i] == 'G')    gFlag = 1 ;
        if (s[i] == 'B')    bFlag = 1 ;

        if (rFlag) {
            int j = lower_bound(B.begin(), B.end(), i) - B.begin() ;
            for ( ; j < B.size(); j++) {
                dist = B[j] - i ;
                int k = lower_bound(G.begin(), G.end(), B[j]) - G.begin() ;
                for ( ; k < G.size(); k++) {
                    if (dist != G[k] - B[j])   ans++ ;
                }
            }

            j = lower_bound(G.begin(), G.end(), i) - G.begin() ;
            for ( ; j < G.size(); j++) {
                dist = G[j] - i ;
                int k = lower_bound(B.begin(), B.end(), G[j]) - B.begin() ;
                for ( ; k < B.size(); k++) {
                    if (dist != B[k] - G[j])   ans++ ;
                }
            }
        }
        else if (gFlag) {
            int j = lower_bound(B.begin(), B.end(), i) - B.begin() ;
            for ( ; j < B.size(); j++) {
                dist = B[j] - i ;
                int k = lower_bound(R.begin(), R.end(), B[j]) - R.begin() ;
                for ( ; k < R.size(); k++) {
                    if (dist != R[k] - B[j])   ans++ ;
                }
            }

            j = lower_bound(R.begin(), R.end(), i) - R.begin() ;
            for ( ; j < R.size(); j++) {
                dist = R[j] - i ;
                int k = lower_bound(B.begin(), B.end(), R[j]) - B.begin() ;
                for ( ; k < B.size(); k++) {
                    if (dist != B[k] - R[j])   ans++ ;
                }
            }
        }
        else if (bFlag) {
            int j = lower_bound(R.begin(), R.end(), i) - R.begin() ;
            for ( ; j < R.size(); j++) {
                dist = R[j] - i ;
                int k = lower_bound(G.begin(), G.end(), R[j]) - G.begin() ;
                for ( ; k < G.size(); k++) {
                    if (dist != G[k] - R[j])   ans++ ;
                }
            }

            j = lower_bound(G.begin(), G.end(), i) - G.begin() ;
            for ( ; j < G.size(); j++) {
                dist = G[j] - i ;
                int k = lower_bound(R.begin(), R.end(), G[j]) - R.begin() ;
                for ( ; k < R.size(); k++) {
                    if (dist != R[k] - G[j])   ans++ ;
                }
            }

        }
        if (s[i] == 'R')    rFlag = 0 ;
        if (s[i] == 'G')    gFlag = 0 ;
        if (s[i] == 'B')    bFlag = 0 ;
    }
    cout << ans ;

    return 0 ;
}


Measured memory_bytes: 3612
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>

int main()
{
	int n;
	scanf("%d", &n);
	std::map<long long, std::vector<int>> mp;
	long long b[200000];
	for (int i = 0; i < n; ++i)
	{
		scanf("%lld", b + i);
		b[i] = i - b[i];
		mp[b[i]].push_back(i);
	}
	long long ans = 0;
	for (int i = 0; i < n - 1; ++i)
	{
		long long search = 2 * i - b[i];
		if (mp.count(search) > 0)
		{
			auto& v = mp[search];
			ans += v.end() - std::upper_bound(v.begin(), v.end(), search);
		}
	}
	printf("%lld\n", ans);
	return 0;
}


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

int main()
{
	double  f, p, l;

	int  a, b, d, r;

	cin >> a >> b;

	p = a;
	l = b;

	d = a / b;
	r = a % b;
	f = p / l;

	cout << d << " " << r << " " << fixed << setprecision(9) << f << endl;


return 0;
}


Measured memory_bytes: 3300
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.NoSuchElementException;

public class Main {
	int L,N;
	int[] x,w;
	ArrayList<Integer>[] list;
	@SuppressWarnings("unchecked")
	public void solve() {
		L = nextInt();
		N = nextInt();
		x = new int[N];
		w = new int[N];

		list = new ArrayList[2 * L + 1];
		for(int i = 0;i < 2 * L + 1;i++){
			list[i] = new ArrayList<Integer>();
		}
		for(int i = 0;i < N;i++){
			x[i] = nextInt();
			w[i] = nextInt();
			list[-x[i] + L].add(w[i]);
		}
		out.println(N);
		for(int i = 0;i < 2 * L + 1;i++){
			for(int weight : list[i]){
				out.println((i-L) + " " + weight);
			}
		}


	}
	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 24512
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int main(){
	int map1[30],map2[30];
	string s,t;
	cin>>s>>t;
	int num,cnt=1;
	vector<int>s2(s.size()),t2(t.size());
	rep(i,30) map1[i]=0,map2[i]=0;
	rep(i,s.size()){
		num=s[i]-'a';
		if(map1[num]==0){
			map1[num]=cnt;
			s2[i]=cnt;
			cnt++;
		}else{
			s2[i]=map1[num];
		}
	}
	cnt=1;
	rep(i,t.size()){
		num=t[i]-'a';
		if(map2[num]==0){
			map2[num]=cnt;
			t2[i]=cnt;
			cnt++;
		}else{
			t2[i]=map2[num];
		}
	}
	int flg=0;
	rep(i,s2.size()){
		if(s2[i]!=t2[i])flg=1;
	}
	if(flg==0)cout<<"Yes\n";
	else cout<<"No\n";
	
	//rep(i,s2.size()) cout<<s2[i]<<" ";
	//rep(i,t2.size()) cout<<t2[i]<<" ";
	return 0;
}

Measured memory_bytes: 2312
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,w;
  cin>>n>>w;
  vector<long long int>value(w+1,0);
   vector<vector<long long int>> X(n+1,value);
  long long int k,v;
  vector<long long int> values;
  vector<long long int> weights;
  values.push_back(0);
  weights.push_back(0);
  for(int i=0;i<n;i++){
  cin>>k>>v;
    values.push_back(v);
    weights.push_back(k);
  }
  for(int i=1;i<n+1;i++){
  for(int j=1;j<w+1;j++){
  	if(j<weights[i]){
    X[i][j]=X[i-1][j];
    }
    else{
      X[i][j]=max(X[i-1][j],values[i]+X[i-1][j-weights[i]]);
    }
  }
  }
  cout<<X[n][w]<<"\n";
}


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

int     main() {
        string S, T;
        cin >>S >>T;
        int s=0;
        for (int i=0; i<3; i++)
                if (S.at(i)==T.at(i))
                        s++;
        cout <<s <<endl;
        return 0;
};

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
inline void read(int &x) {
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 2220, M = 2040030, inf = 0x3f3f3f3f;
int S,T,head[N],cur[N],nxt[M],cap[M],to[M],edgenum=1; //1.WA£¨ÆäËüµØ·½Ó¦¸Ã¶¼²»ÈÝÒ×Ð´¹Ò£©--edgenum=1!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
void addedge(int u, int v, int c){
	to[++edgenum]=v;cap[edgenum]=c;nxt[edgenum]=head[u];head[u]=edgenum;
}
void add(int u, int v, int c){
	addedge(u,v,c);addedge(v,u,0);
}
int dis[N],q[N];
inline bool bfs() {
	memset(dis,inf,4*(T+2));//2.memset²»ÓÃsizeof()
	int f=0,r=1; q[f]=T; dis[T]=0;
	while (f!=r) {
		int u=q[f++];
		L(i,u) if (cap[i^1]&&dis[to[i]]==inf){
			q[r++]=to[i];dis[to[i]]=dis[u]+1;if(to[i]==S)return 1;//3.¼ôÖ¦
		}
	}
	return dis[S]<inf;
}
inline int dfs(int u, int flow) {
	if (u==T||!flow)return flow;int res=0;
	for(register int &i=cur[u];i;i=nxt[i])if(cap[i]&&dis[u]==dis[to[i]]+1){//4.µ±Ç°»¡ 
		int tmp=dfs(to[i],min(flow,cap[i]));
		res+=tmp;flow-=tmp;cap[i]-=tmp;cap[i^1]+=tmp;if(!flow)break;
	}
	return res;
}
inline int dinic() {
	int res=0;
	while (bfs()) {
		memcpy(cur,head,4*(T+2)); res+=dfs(S,inf);
	}
	return res;
}
set<int>Set;
Vi a,b;int n;
int prime[10020000],len,mrk[10020000];
int Abs(int x){return x>0?x:-x;}
void getp(int n){
	rep(i,2,n){
		if(!mrk[i])prime[++len]=i;
		rep(j,1,len){
			if(i*prime[j]>n)break;
			mrk[i*prime[j]]=prime[j];
			if(i%prime[j]==0)break;
		}
	}
	mrk[1]=1;
}
int main() {
	getp(1e7);read(n);rep(i,1,n){
		int x;read(x);
		if(!Set.count(x))Set.insert(x);else Set.erase(x);
		x++;
		if(!Set.count(x))Set.insert(x);else Set.erase(x);
	}
	while(!Set.empty()){
		int x=*Set.begin();Set.erase(x);
		if(x&1)a.pb(x);else b.pb(x);
	}
	S=SZ(a)+SZ(b)+3;T=S+1;
	rep(i,0,SZ(a)-1)add(S,i+1,1);
	rep(i,0,SZ(b)-1)add(SZ(a)+i+1,T,1);
	rep(i,0,SZ(a)-1)rep(j,0,SZ(b)-1)if(!mrk[Abs(a[i]-b[j])])
		add(i+1,SZ(a)+j+1,1);
	int res=dinic();
//	cerr<<SZ(a)<<' '<<SZ(b)<<' '<<res<<endl;
	if(SZ(a)-res&1)cout<<res+SZ(a)-res+SZ(b)-res+1;
	else cout<<res+SZ(a)-res+SZ(b)-res;
	return 0;
}

Measured memory_bytes: 49536
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <iomanip>
#include <queue>
#include <vector>

using namespace std;

#define REP(I,A,B) for(int I = (A); I < (B); ++I)
#define REPN(I,A,B) for(int I = (A); I > (B); --I)
#define MAX(A,B) ((A) > (B) ? (A) : (B));

int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};

int rb[200000];
int lb[200000];

long long solve(int * p, int n) {
	long long cnt = 0;
	vector<int> st;
	REP(i, 0, n){
		while(!st.empty() && p[st.back()] > p[i])
			st.pop_back();
		if (st.empty())
			lb[i] = -1;
		else
			lb[i] = st.back();
		st.push_back(i);
	}
	st.clear();
	REPN(i, n - 1,-1) {
		while(!st.empty() && p[st.back()] > p[i])
			st.pop_back();
		if (st.empty())
			rb[i] = n;
		else
			rb[i] = st.back();
		st.push_back(i);
	}

	REP(i,0,n) {
		cnt += p[i] * (long long)(i - lb[i]) * (long long)(rb[i] - i);
	}
	return cnt;
}

int main() {
	int n;
	cin >> n;
	int p[200000];
	REP(i, 0, n)
		cin >> p[i];
	cout << solve(p, n) << endl;
	return 0;
}

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;



ll N;

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

    cin>>N;

    for (ll w=1; w<=3500; w++) {
	for (ll h=1; h<=3500; h++) {
	    ll num = N*h*w;
	    ll den = 4ll*h*w-N*w-N*h;
	    if (den<=0) {
		continue;
	    }
	    if (num%den) continue;
	    ll n = num/den;
	    cout<<h<<" "<<n<<" "<<w<<endl;
	    exit(0);
	}
    }

    assert(false);
    
    
    return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep2(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define pb push_back
#define COUT(x) cout << (x) << endl
#define COUTF(x) cout << setprecision(15) << (x) << endl
#define ENDL cout << endl
#define DF(x) x.erase(x.begin())  // 先頭文字削除
#define ALL(x) x.begin(), x.end()
#define SORT(x) sort(ALL(x))
#define REVERSE(x) reverse(ALL(x))
#define init() \
  cin.tie(0);  \
  ios::sync_with_stdio(false)
#define debug(x) cerr << "[debug] " << #x << ": " << x << endl;
#define debugV(v)                       \
  cerr << "[debugV] " << #v << ":";     \
  rep(i, v.size()) cerr << " " << v[i]; \
  cerr << endl;
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using P = pair<ll, ll>;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr ld PI = 3.141592653589793238462643383279;
ll get_digit(ll x) {
  return to_string(x).size();
}

ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

vector<P> factorize(ll n) {
  vector<P> result;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      result.pb({i, 0});
      while (n % i == 0) {
        n /= i;
        result.back().second++;
      }
    }
  }
  if (n != 1) {
    result.pb({n, 1});
  }
  return result;
}

vll divisor(ll n) {
  vll ret;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  SORT(ret);
  return (ret);
}

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

signed main() {
  init();
  string S;
  cin >> S;

  ll ans = 0;
  rep(i, S.size()) {
    if (S[i] == '+') {
      ans++;
    } else {
      ans--;
    }
  }
  COUT(ans);
  return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <clocale>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = (s), i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = (s), i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = (s); i < (n); ++i)
#define VFORS(i, s, n) for(int i = (s); i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = (s), i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = (s), i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define REV(x) reverse(ALL(x))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

using ld = long double;
using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using Pi_i = pair<int, int>;
using Pll_ll = pair<ll, ll>;
using VB = vector<bool>;
using VC = vector<char>;
using VD = vector<double>;
using VI = vector<int>;
using VLL = vector<ll>;
using VS = vector<string>;
using VSH = vector<short>;
using VULL = vector<ull>;

const int MOD = 1000000007;
const int INF = 1000000000;
const int NIL = -1;
const double EPS = 1E-10;

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


int main(){
    int N; cin >> N;
    int prv(INF + 3), cnt(0), flg(1);
    // flg 0:未確定、 1:非減少 、 2:非増加
    REP(i, N){
        int A; cin >> A;
        if(!flg){
            if(prv > A) flg = 2;
            else if(prv < A) flg = 1;
        }
        else if(flg == 1 && prv > A){
            ++cnt; flg = 0;
        }
        else if(flg == 2 && prv < A){
            ++cnt; flg = 0;
        }
        prv = A;
    }
    cout << cnt << endl;
    return 0;
}


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

public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		
		int N = scan.nextInt();
		
		String str = "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51";
        String[] strArray = str.split(",");
        System.out.println(strArray[N-1]);
    }
}

Measured memory_bytes: 22996
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main()
{
    int A,B,K,tmpA,tmpB;
    scanf("%d %d %d",&A,&B,&K);
    int k2=0;
    while( 1 ){
        if( A % 2 == 1 ) A--;
        B += A / 2;
        A -= A / 2;
        k2++;
        if( k2 == K ){
            printf("%d %d\n",A,B);
            return 0;
        }
        if( B % 2 == 1 ) B--;
        A += B / 2;
        B -= B / 2;
        k2++;
        if( k2 == K ){
            printf("%d %d\n",A,B);
            return 0;
        }
    }

}

Measured memory_bytes: 128