akhauriyash/Code-Regression huggingface dataset:
/*
* @Author: _dp95
* @Date:   2020-04-12 09:28:33
*/
#include "bits/stdc++.h"
using namespace std ;

#define timesaver ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef long long ll ;
typedef long double ldb ;

#define mp make_pair
#define pb push_back
#define F first
#define S second
#define nl '\n'

#define all( x ) x.begin(),x.end() 
#define sz( x ) ( int )( x ).size( )
#define mem( a, val ) memset(a, val, sizeof( a ) )
#define deci( x ) cout<<fixed<<setprecision( x );
#define bitcount( x ) __builtin_popcountll( x )

const int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

const int MAX = 2*1000*1000 + 10 ;
const ll INF = 1e18 ;
const int MOD = 1e9 + 7 ;

signed main( ){
  timesaver ;
  int n, ans(0) ;
  cin >> n ;
  vector< int > v(n) ;
  for( int &i : v ){
    cin >> i ;
    ans += i ;
  }
  int q ;
  cin >> q ;
  while( q-- ){
    int i, x ;
    cin >> i >> x ;
    i-- ;
    int tmp = ans - v[i] + x ;
    cout << tmp << nl ;
  }
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
R,C,K=map(int, sys.stdin.readline().split())

value=defaultdict(lambda: 0)
value=[ [0 for _ in range(C+1)] for __ in range(R+1) ]
for _ in range(K):
    r,c,v=map(int, sys.stdin.readline().split())
    value[r][c]=v

dp0=[0]*(C+1)
dp1=[0]*(C+1)
dp2=[0]*(C+1)
dp3=[0]*(C+1)

for r in range(1,R+1):
    for c in range(1,C+1):
        #今のマスにアイテムがある場合
        if 0<value[r][c]:
            dp3[c]=max( dp3[c-1], dp2[c-1]+value[r][c] )
            dp2[c]=max( dp2[c-1], dp1[c-1]+value[r][c] )
            dp1[c]=max( dp1[c-1], dp0[c-1]+value[r][c], dp0[c]+value[r][c] )
            dp0[c]=max( dp0[c-1], dp0[c] )
        #今のマスにアイテムがない場合
        else:
            #dp0[c]=max( dp0[c-1], dp0[c] )
            #dp1[c]=max( dp1[c-1], dp1[c] )
            #dp2[c]=max( dp2[c-1], dp2[c] )
            #dp3[c]=max( dp3[c-1], dp3[c] )
            dp0[c]=max( dp0[c-1], dp0[c] )
            dp1[c]=dp1[c-1]
            dp2[c]=dp2[c-1]
            dp3[c]=dp3[c-1]

    #上の行にアイテムをコピー
    for c in range(1,C+1):
        dp0[c]=max( dp0[c], dp1[c], dp2[c], dp3[c] )
    dp1=[0]*(C+1)
    dp2=[0]*(C+1)
    dp3=[0]*(C+1)

print dp0[C]


Measured memory_bytes: 152580
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

    int n;
    cin >> n;

    int b = 1, p = 0;
    for (int i = 0; i < n; i++) {
        int h;
        cin >> h;

        if (p <= h - 1) h--;
        if (p > h) {
            b = 0;
            break;
        }
        p = h;
    }

    cout << (b ? "Yes" : "No") << endl;

    //低くしてその後損しない

    return 0;
}

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

int main() {
    vector <int> v(26);
    string s; cin >> s;
    int index,flag = 0;
    fill (v.begin(),v.end(),0);
    for (int i = 0; i <(int)s.size();i++) {
        index = s[i]-'a';
        v[index]++;
        if(v[index] > 1){
            flag = 1;
            break;
        }
    }
    if (flag == 0)
        cout <<"yes"<<endl;
    else
        cout << "no"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define ll long long
#define mod 1000000007
const int MAX=1e6+1;
ll fac[MAX],finv[MAX],inv[MAX];
ll power(ll x, ll y) 
{ 
    if (y == 0) 
        return 1; 
    ll p = power(x, y/2) % mod; 
    p = (p * p) % mod; 
  
    return (y%2 == 0)? p : (x * p) % mod; 
} 
 
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;
    finv[i]=finv[i-1]*power(i,mod-2)%mod;
  }
}
int main()
{
 	COMinit(); 
	int x,y;
    cin>>x>>y;
    int sum=x+y;
    ll ans=0;
    if(sum%3==0)
    {
        ll count=sum/3;
        for(int i=0;i<=count;i++)
        {
            ll one=i;
            ll two=count-i;
            ll s=one+two*2;
            if(s==x||s==y)
            {
                ans=(((fac[count]*finv[one])%mod)*finv[two])%mod;
                break;
            }
        }
    }
    cout<<ans%mod<<endl;//cout<<3*infact[2]%mod<<endl;
	return 0;
}

Measured memory_bytes: 17536
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public static class Input
{
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}

class Program
{
    static int N, K;
    static int[] h;

    public static void Main(string[] args)
    {
        N = Input.NextInt();
        K = Input.NextInt();
        h = new int[N];
        for (int i = 0; i < N; i++)
            h[i] = Input.NextInt();

        Array.Sort(h);
        Array.Reverse(h);
        int min = int.MaxValue;
        for (int i = 0; i <= h.Length - K; i++)
        {
             min = Math.Min(min, h[i] - h[i + K - 1]);
        }

        Console.WriteLine(min);
    }
}


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

using namespace std;

#define umap std::unordered_map
#define uset std::unordered_set
#define _all(container) std::begin(container), std::end(container)
#define _in(container, value) (std::find(_all(container), value) != std::end(container))
#define _in_if(container, predicate) (std::find_if(_all(container), predicate) != std::end(container))
#define _odd(value) (value & 1)
#define _even(value) !(value & 1)
#define _for(i, n) (for (int i = 0; i < n; ++i))
#define _FOR(i, k, n) (for (int i = k; i <= n; ++i))
#define _FORR(i, k, n) (for (int i = n; i >= k; --i))

using Integer = long long;
using vint = vector<int>;
using pint = pair<int, int>;
using vpint = vector<pint>;
using vdouble = vector<double>;
using cint = const int;
using cdouble = const double;

void solve()
{
    int P, Q, R;
    cin >> P >> Q >> R;

    cout << min(P + Q, min(P + R, Q + R)) << "\n";
}

int main(int argc, char**)
{
    if (argc > 1) {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();
}


Measured memory_bytes: 256
# coding: utf-8
import numpy as np

n, k = map(int, input().split())
h_list = np.array([int(x) for x in input().split()])

ans = np.zeros(n, dtype=int)

for i in range(1, n):
    start = max(i-k, 0)
    ans[i] = np.min(ans[start:i] + np.abs(h_list[start:i] - h_list[i]))
        
# print(ans)
print(ans[-1])

Measured memory_bytes: 23084
#ifdef __GNUC__
#pragma GCC target("avx2")
#pragma GCC optimize ("O20")
#pragma GCC optimize ("tree-vectorize")
#pragma GCC optimize("unroll-loops")
#endif
#include "bits/stdc++.h"
#define rep(i, times) for(ll i = 0; i < (times); ++i)
#define p(x) (cout << x << "\n")
using ll = uint16_t; using ld = long double; using namespace std;

int main( ) {
	cin.tie(0);	ios::sync_with_stdio(0);
	ll N; cin >> N;
	vector<ll> P(N), q(N);
	rep(n, N) { cin >> P[n]; }
	rep(n, N) { cin >> q[n]; }
	long long sa{0};
	if (P > q) swap(P, q);
	do {
		if (P == q) break;
		++sa;
	} while (next_permutation(begin(P), end(P)));
	p(sa);
}

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

using namespace std;

typedef long long llint;

const llint MAXN = 5005;
const llint MOD = 1000000007;

llint m, n;
string s;
int dp[MAXN*2][MAXN];

int f (int x, int y) {
    if (y == 0) return (x == 0);
    if (dp[x][y] != -1) return dp[x][y];
    if (x == 0) return dp[x][y] = (f(x+1, y-1) + f(x, y-1)) % MOD;
    return dp[x][y] = (f(x+1, y-1) + 2*f(x-1, y-1)%MOD) % MOD;
}

int main () {
    memset(dp, -1, sizeof dp);
    cin >> n >> s;
    llint m = s.size();
    llint sol = f(m, n);
    for (llint i=0; i<m; i++) sol = (sol * (MOD + 1)/2) % MOD;
    cout << sol;
    return 0;
}


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

using namespace std;

using u128 = __uint128_t;

#define int long long
#define MOD 1000000007

int solve(const int *spell, const int *cost, int n, int k){
    int dp[k+1];
    for(int i = 0 ; i<= k ; i++) dp[i] = LONG_LONG_MAX;
    dp[0] = 0;
    for(int i = 1; i<= k; i++){
        for(int j = 0; j < n ; j++){
            int temp = (i - spell[j])  < 0 ? cost[j] : cost[j] + dp[i - spell[j]];
            dp[i] = min(dp[i] , temp);
        }
    }
    return dp[k];
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int h, n;
    cin>>h>>n;
    int *spell = new int[n];
    int *cost = new int[n];
    for(int i = 0; i < n; i++){
        cin>>spell[i] >> cost[i];
    }
    cout<<solve(spell, cost, n, h);

    return 0;
}

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

int main(){
    int a;
    cin>>a;
    int ma=0;
    int mi=1001;
    for(int i=0;i<a;i++){
		int b[100];
		cin>>b[i];
		ma=max(ma,b[i]);
		mi=min(mi,b[i]);
	}
	cout<<ma-mi<<endl;
}


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

typedef long long ll;
const ll INF = 1e9, MOD = 1e9 + 7;
const double EPS = 1e-9, PI = 3.141592653589793;
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define REPR(i,a,b) for(ll i=b;i>=a;i--)
#define repr(i,n) REPR(i,0,n)
#define All(v) (v).begin(), (v).end()
#define Pb push_back

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

    string s;
    cin >> s;
    ll size,flag=1;
    size = s.size();
    set<char> st;
    rep(i,size) st.insert(s[i]);
    if(st.count('N')==1){
        if(st.count('S')==1){
            if(st.count('E')==1){
                if(st.count('W')==1){
                    cout << "Yes" << "\n";
                }else{
                    cout << "No" << "\n";
                }
            }else{
                if(st.count('W')==0){
                    cout << "Yes" << "\n";
                }else{
                    cout << "No" << "\n";
                }
            }
        }else{
            cout << "No" << "\n";
        }
    }else{
        if(st.count('S')==0){
            if(st.count('E')==1){
                if(st.count('W')==1){
                    cout << "Yes" << "\n";
                }else{
                    cout << "No" << "\n";
                }
            }else{
                if(st.count('W')==0){
                    cout << "Yes" << "\n";
                }else{
                    cout << "No" << "\n";
                }
            }
        }else{
            cout << "No" << "\n";
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int x,a,b;
  cin >> x >> a >> b;
  if(abs(x-a)>abs(x-b))
  {
    cout << "B" << endl;
  }
  else
  {
    cout << "A" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const int INF = 1001001001;
int main(){
    int h, n;
    cin >> h >> n;
    vector<int> dp(h + 1, INF);
    dp[0] = 0;
    rep(i, n){
        int a, b;
        cin >> a >> b;
        rep(j, h){
            int nj = min(j + a, h);
            dp[nj] = min(dp[nj], dp[j] + b);
        }
    }
    cout << dp[h] << endl;
    return 0;
}

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

int main()
{
    int a[50] = {0,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};
    int n;
    cin >> n;
    cout << a[n] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
 
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;
 
#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second
 
int main(int argc, char **argv) {
	string s;
	cin >> s;
	sort(ALL(s));
	cout << (s == "abc" ? "Yes" : "No") << endl;
	return 0;
}
 

Measured memory_bytes: 256
/**
 * C - 755
 * https://atcoder.jp/contests/abc114/tasks/abc114_c
 **/
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

#define ll long long

bool is_753(string s) {
    return (s.find('7')!=string::npos)&(s.find('5')!=string::npos)&(s.find('3')!=string::npos);
}

ll dfs(string s, ll n) {
    ll s_num = atoll(s.c_str());
    if(s_num>n) return 0;
    ll ret = 0;
    if(is_753(s)) ret = 1;
    string str="357";
    for(auto c:str) {
        ret += dfs(s+c, n);
    }
    return ret;
}


int main() {
    ll n; cin >> n;
    cout << dfs("0", n) << endl;
    return 0;
}

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

int main()
{
    string s;
    cin >> s;
    bool flag1 = true, flag2 = true, flag3 = true;
    int n = s.length(), n1 = (s.length()-1)/2, n2 = (s.length()+3)/2;
    for(int i=0; i<n; i++)
        if(s[i]!=s[n-i-1])
            flag3 = false;
    for(int i=0; i<n1/2; i++)
        if(s[i]!=s[n1-i-1])
            flag1 = false;
    for(int i=n2-1; i<n; i++)
        if(s[i]!=s[n-i-1])
            flag2 = false;
    if(flag1&&flag2&&flag3) cout << "Yes";
    else cout << "No";
    return 0;
}

Measured memory_bytes: 256
def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n
p, q = map(int, input().split())
q //= gcd(p, q)

x = q; y = 1; k = 2
while k*k <= x:
    if x % k == 0:
        while x % k == 0: x //= k
        y *= k
    k += 1
y *= x

print(y)

Measured memory_bytes: 7728
N = int(input())
A = [0] + list(map(int, input().split())) + [0]

total = sum([abs(A[i-1] - A[i]) for i in range(N+2)])

for i in range(1, N+1):
    n = total - abs(A[i-1] - A[i]) - abs(A[i] - A[i+1])
    n += abs(A[i-1] - A[i+1])
    print(n)

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

// macros
#define overload_rep(va_0, va_1, va_2, va_3, name, ...) name
#define rep_0_(i, n) for(int i = 0; i < (n); ++i)
#define rep_1_(i, x, y) for(int i = (x); i <= (y); ++i)
#define rep_2_(i, x, y, z) for(int i = (x); i >= (y); --i)
#define rep(...) overload_rep(__VA_ARGS__, rep_2_, rep_1_, rep_0_)(__VA_ARGS__)
#define all(a) a.begin(), a.end()
#ifndef STOP_DEBUG
#define debug(...)\
    do { cerr << boolalpha << "[" << #__VA_ARGS__ << "]:";\
    debug_cerr(__VA_ARGS__); cerr << noboolalpha; } while (0)
#else
#define debug(...)
#endif

// functions
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 debug_cerr(){ cerr << '\n'; }
template<class Head, class... Tail>
void debug_cerr(Head head, Tail... tail){
    cerr << ' ' << head;
    debug_cerr(tail...);
}

// cin/cout setup
struct IoSetup{
    IoSetup(){
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} iosetup;

// libraries

// declarations

// solve
int main(){

    int a;
    cin >> a;
    cout << a * a << '\n';

}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { 
  INIT(){cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


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

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

  int ans = INF;
  REP(k, 105){
    int ret = 0;
    REP(i, N){
      ret += (A[i]-k)*(A[i]-k);
    }
    chmin(ans, ret);
  }
  cout << ans << "\n";

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ul;
typedef signed long long ll;
ul over = 1000000007;

mt19937 mt(time(nullptr));
// uniform_int_distribution< int > rand_int(0, 10) // rand[0, 10] inclusive

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed;
  int n, k;
  string s;
  cin >> n >> k >> s;
  k--;
  if (s[k]=='A') s[k]='a';
  if (s[k]=='B') s[k]='b';
  if (s[k]=='C') s[k]='c';
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define shosu(n) setprecision(n)
#define INF 999999999
using namespace std;
int main() {
  int y, s, i;
  int c[] = {10, 50, 100, 500};
  int N[4];
  bool key = false;
  while (cin >> y, y) {
    s = -y;
    if (key)
      cout << endl;
    for (i = 0; i < 4; i++) {
      cin >> N[i];
      s += c[i] * N[i];
    }
    for (i = 3; i >= 0; i--) {
      while (s >= c[i]) {
        s -= c[i];
        N[i]--;
      }
    }
    for (i = 0; i < 4; i++) {
      if (N[i] > 0) {
        cout << c[i] << " " << N[i] << endl;
      }
    }
    key = true;
  }
  return 0;
}

Measured memory_bytes: 2996
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

// 計算済みの結果は再利用するようにする。
public class Main {

    private int redNum;
    private int blueNum;
    private static long MOD = (long)(Math.pow(10,9) + 7);
    private static int ARRAY_NUM = 2048;
    private long[][] memo = new long[ARRAY_NUM][ARRAY_NUM];

    private void solve() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        redNum = N - K;
        blueNum = K;

        for (int i = 0; i < ARRAY_NUM; i++) {
            for (int j = 0; j < ARRAY_NUM; j++) {
                memo[i][j] = -1;
            }
        }
        for (int i = 1; i <= K; i++) {
            double count = calcCount(i);
            System.out.println((int)(count));
        }
    }

    private long calcCount(int i) {
        long posCntToPlaceBlue = calcNumOfCombination(redNum + 1, i);
        long splitCntOfBlue = calcNumOfCombination(blueNum - 1, i - 1);
        long ansCount = posCntToPlaceBlue * splitCntOfBlue % MOD;
        //long ansCount = posCntToPlaceBlue * splitCntOfBlue;
        return ansCount;
    }

    // 計算結果をmodしても、先にmodしてから計算しても、結果は同じ。
    private long calcNumOfCombination(int n, int r) {
        if (n == r) {
            memo[n][r] = 1;
            return memo[n][r];
        }
        else if (n < r) {
            memo[n][r] = 0;
            return memo[n][r];
        }
        else if (memo[n][r] != -1) {
            return memo[n][r];
        }
        else if (((n - r) >= 0) && (memo[n][n - r] != -1)) {
            return memo[n][n - r];
        }
        else {
            BigInteger result = BigInteger.valueOf(1);
            for (int i = 1; i <= r; i++) {
                result = result.multiply(BigInteger.valueOf(n - (i - 1))).divide(BigInteger.valueOf(i));
            }
            memo[n][r] = result.mod(BigInteger.valueOf(MOD)).longValue();
            return memo[n][r];
        }
    }

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

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

#define FOR(a,b,c) for (int a=(b);a<(c);++a)
#define REP(i,n) FOR(i,0,n)
#define ll long long
#define pii pair<int,int>
#define x first
#define y second
#define pb push_back
#define lf double

using namespace std;

const int MAX = (int)1e6 + 5;

int sol;
ll a;

void f(int d){
	int cnt=0;
	while(a%d==0){
		a/=d;
		cnt++;
	}
	for (int i=1;i<100;++i){
		cnt-=i;
		if (cnt>=0) sol++;
	}
}

int main(){
	scanf ("%lld",&a);
	for (ll i=2;i*i<=a;++i){
		f(i);
	}
	if (a>1) sol++;
	printf ("%d\n",sol);
	return 0;
}


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

#define int long long

template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if ( a > b ) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if ( a < b ) a = b; }

using Pii = pair<int, int>;

const int INF = 1e18;

struct Edge {
  int t, w;
  Edge(){}
  Edge(int t, int w): t(t), w(w) {}  
};

vector<Edge> G[100001];
int n, d[100001];
int st, ds;

void bfs(int s) {
  for ( int i = 0; i < n; i++ ) d[i] = INF;
  queue<int> q;
  q.push(s);
  d[s] = 0;
  int u;
  while ( !q.empty() ) {
    u = q.front(); q.pop();
    for ( int i = 0; i < (int)G[u].size(); i++ ) {
      Edge e = G[u][i];
      if ( d[e.t] == INF ) {
	d[e.t] = d[u]+e.w;
	q.push(e.t);
      }
    }
  }
}

void calc_d() {  
  bfs(0);
  int maxv = 0;
  st = 0; ds = 0;
  for ( int i = 0; i < n; i++ ) {
    if ( d[i] == INF ) continue;
    if ( maxv < d[i] ) {
      maxv = d[i];
      st = i;
    }
  }

  bfs(st);
  maxv = 0;
  for ( int i = 0; i < n; i++ ) {
    if ( d[i] == INF ) continue;
    if ( maxv < d[i] ) {
      maxv = d[i];
      ds = i;
    }
  }
}

int pre[100001];
bool is_body[100001];
vector<int> path;
void calc_path(int v, int p) {
  pre[v] = p;
  for ( int i = 0; i < (int)G[v].size(); i++ ) {
    Edge e = G[v][i];
    if ( e.t == p ) continue;
    calc_path(e.t, v);
  }
}

bool is_caterpillar() {
  for ( int i = 0; i < (int)path.size(); i++ ) {
    for ( int j = 0; j < (int)G[path[i]].size(); j++ ) {
      int v = G[path[i]][j].t;      
      if ( is_body[v] ) continue;
      if ( (int)G[v].size() > 1 ) return false;
    }
  }

  return true;
}

signed main() { 
  cin >> n;
  for ( int i = 0; i < n-1; i++ ) {
    int v, w;
    cin >> v >> w;
    v--; w--;
    G[v].push_back(Edge(w, 1));
    G[w].push_back(Edge(v, 1));
  }
  
  calc_d();

  calc_path(st, -1);
  {
    int v = ds;
    while ( v != -1 ) {      
      path.push_back(v);
      is_body[v] = true;
      v = pre[v];
    }
  }

  if ( !is_caterpillar() ) {
    cout << -1 << endl;
    exit(0);
  }

  vector<int> ans1, ans2;
  int idx = 1;
  for ( int i = 0; i < (int)path.size(); i++ ) {
    int tmp = idx;
    idx++;
    for ( int j = 0; j < (int)G[path[i]].size(); j++ ) {
      int v = G[path[i]][j].t;     
      if ( is_body[v] ) continue;
      ans1.push_back(idx++);
    }
    ans1.push_back(tmp);
  }

  idx = 1;
  for ( int i = (int)path.size()-1; i >= 0; i-- ) {
    int tmp = idx;
    idx++;
    for ( int j = 0; j < (int)G[path[i]].size(); j++ ) {
      int v = G[path[i]][j].t;     
      if ( is_body[v] ) continue;
      ans2.push_back(idx++);
    }
    ans2.push_back(tmp);
  }

  vector<int> ans = min(ans1, ans2);

  for ( int i = 0; i < n; i++ ) {
    if ( i ) cout << " ";
    cout << ans[i];
  }
  cout << endl;
  
  return 0;
}


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

using i64 = int_fast64_t;
using f64 = double;

void solve() {
    i64 n, a, b;
    cin >> n >> a >> b;
    i64 d = b - a;
    cout << (d % 2 == 0 ? d / 2 : min(n - b + (d + 1) / 2, a - 1 + (d + 1) / 2)) << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl '\n'
#define rep(i,n) for(int i=0;i<n;i++) 
#define all(v) v.begin(),v.end()
#define F first
#define S second 
const ll MOD=1e9+7;
template<typename ForwardIterator,typename T>
ForwardIterator first_less_than(ForwardIterator first,ForwardIterator last,T val)
{
	auto it=lower_bound(first,last,val);
	return (it==first?first:it);
}

void solve()
{
	ll n;
	cin>>n;
	ll arr[n];
	rep(i,n)
	{
		cin>>arr[i];
	}
	ll res[n];
	res[n-1]=arr[n-1]%MOD;
	for(int i=n-2;i>=0;i--)
	{
		res[i]=(res[i+1]+arr[i])%MOD;
	}
	ll sum=0;
	for(int i=0;i<n-1;i++)
	{
		sum+=((arr[i]%MOD)*(res[i+1])%MOD)%MOD;
	}
	cout<<sum%MOD<<endl;
	
}

int main()
{
	ios_base::sync_with_stdio(false); 
  	 cin.tie(NULL);  
	int tt;
	tt=1;
	while(tt--)
	{
		solve();
	}
}


Measured memory_bytes: 6776
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long max = Math.max(a, b);
        int sqrt = (int) Math.sqrt(max)+1;
        boolean[] used = new boolean[sqrt+1];
        int ans = 1;
        for (int i = 2; i <= sqrt; i++) {
            if(used[i])continue;
            if(a  % i == 0 && b % i == 0) ans++;
            for (int j = i; j <= sqrt; j += i) {
                used[j] = true;
            }
            while(max % i == 0) max /= i;
        }
        if(1 < max && a % max == 0 && b % max == 0) ans++;
        System.out.println(ans);
        sc.close();

    }

}


Measured memory_bytes: 26196
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)n - 1; i > -1; i--)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ld long double
typedef pair<ll, ll> pll;

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

    vector<ll> A(4);
    rep(i, 4) { cin >> A[i]; }

    ll ans = -LLONG_MAX;
    for (int i = 0; i <= 1; i++) {
        for (int j = 2; j < 4; j++) {
            ans = max(ans, A[i] * A[j]);
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3648
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
#define INF 1e8
typedef long long ll;
using namespace std;
//オーバーフローに気をつけろよおおおおおお
//確認忘れるなよおおおおおお

int main() {
    int n; cin >> n;
    map<int, int> m;
    rep(i,n){
        int num; cin >> num;
        if(m[num]==0) m[num] += 1;
        else m[num] = 0;
    }
    int ans = 0;
    for(auto a : m){
        if(a.second==1) ans += 1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4864
#include <bits/stdc++.h>
#define sz(c)       int(c.size())
#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 fore(c,...) for (auto &__VA_ARGS__:(c))
using namespace std;
using ll = long long;

int const MD=int(1e9)+7;

int madd(int x,int y) {
	if (x+y<MD) return x+y; else return x+y-MD;
}
int msub(int x,int y) {
	if (x-y>=0) return x-y; else return x-y+MD;
}
int mmul(int x,int y) {
	return int(ll(x)*y % MD);
}
int mpow(int x,int p) {
	int res=1;
	while (p>0) {
		if (p%2) res=mmul(res,x);
		x=mmul(x,x);
		p/=2;
	}
	return res;
}
int minv(int x) {
	return mpow(x,MD-2);
}
int mdiv(int x,int y) {
	return mmul(x,mpow(y,MD-2));
}

struct mod_fact {
	vector<int> f,rf;
	mod_fact(int n):f(n),rf(n) {
		f[0]=rf[0]=1;
		rep(i,1,n) {
			f[i]=mmul(f[i-1],i);
			rf[i]=minv(f[i]);
		}
	}
} mfact(110'000);
int comb(int n,int k) {
	if (n<k) return 0;
	return mmul(mfact.f[n],mmul(mfact.rf[n-k],mfact.rf[k]));
}
int distr(int n,int k) {
	return comb(n+k-1,k-1);
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	int N,K;
	cin>>N>>K;
	vector<int> a(N);
	fore(a,i) cin>>i;

	map<int,int> cnt;
	fore(a,i) cnt[i]++;

	int sum=0,res=0;
	fore(cnt,p) {
		sum+=p.second;
		if (sum>=K) {
			int c=msub(comb(sum,K),comb(sum-p.second,K));
			res=madd(res,mmul((p.first+MD)%MD,c));
		}
	}

	sum=0;
	for (auto it=cnt.rbegin(); it!=cnt.rend(); it++) {
		auto p=*it;
		sum+=p.second;
		if (sum>=K) {
			int c=msub(comb(sum,K),comb(sum-p.second,K));
			res=msub(res,mmul((p.first+MD)%MD,c));
		}
	}

	cout<<res<<'\n';
}


Measured memory_bytes: 5888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
vector<ll> ans(2001,0);
 
int main(){
    ans.at(0) = 1;
    ll s; cin >> s;
    for(int i=3;i<=s;i++){
        ll x = 0;
        for(int j=0;j<=i-3;j++){
            x = (x+ans.at(j))%mod;
        }
      	ans.at(i)=x;
    }
    cout << ans.at(s);
    return 0;
}

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

bool check(string s){
	int cnt[26] = { 0 };
	for(auto c : s){
		int i = c - 'a';
		if(cnt[i]) return false;
		cnt[i]++;
	}
	return true;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	string s;
	cin >> s;

	string ans = string(30, 'z');
	for(int i = 0; i < 26; i++){
		string ss = s + char('a' + i);
		if(check(ss) && ss > s && ans > ss){
			ans = ss;
		}
	}

	for(int i = 0; i < s.size(); i++){
		for(int j = 1; j + s[i] <= 'z'; j++){
			string ss = s;
			ss[i] += j;
			ss = ss.substr(0, i + 1);
			if(check(ss) && ss > s && ans > ss){
				ans = ss;
			}
		}
	}

	if(ans.size() == 30){
		cout << -1 << endl;
	}
	else{
		cout << ans << endl;
	}
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <iterator>
#include <cmath>
#include <deque> 

using namespace std;


bool inATCG(char ch)
{
	if (ch == 'A' || ch == 'T' || ch == 'C' || ch == 'G')
		return true;
	else
		return false;
}

int main()
{
	char s[20];
	int n;
	scanf("%s", s);
	
	n = strlen(s);
	
	int maxLen = 0;
	int l = 0;
	int h = 0;
	while (l < n)
	{
		while (l < n && (inATCG(s[l]) == false))
			l++;
		if (l >= n)
			break;
			
		h = l;
		while (h < n && (inATCG(s[h]) == true))
			h++;
		h--;	//always one more
			
		int curLen = h - l + 1;
		if (curLen > maxLen)
			maxLen = curLen;
			
		l = h + 1;
	}
	
	printf("%d\n", maxLen);
	
	
	return 0;
}


Measured memory_bytes: 128
#include<functional>
#include<algorithm>
#include<exception>
#include<stdexcept>
#include<streambuf>
#include<iterator>
#include<string.h>
#include<stdlib.h>
#include<typeinfo>
#include<valarray>
#include<iostream>
#include<sstream>
#include<istream>
#include<stdio.h>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<ctype.h>
#include<cassert>
#include<cstdlib>
#include<utility>
#include<cstring>
#include<numeric>
#include<ostream>
#include<cwctype>
#include<fstream>
#include<iomanip>
#include<math.h>
#include<bitset>
#include<cctype>
#include<string>
#include<vector>
#include<limits>
#include<locale>
#include<memory>
#include<cerrno>
#include<time.h>
#include<iosfwd>
#include<cfloat>
#include<cstdio>
#include<cwchar>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<ios>
#include<map>
#include<set>
#include<new>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define MP make_pair
#define all(x) (x.begin(),x.end())
using namespace std;
typedef long long ll;
const int INF=1e9+7;
int n;
vector<ll> a,b,c;
void in(vector<ll> x)
{
	int m;
	for (int i=1;i<=n;i++)
	{
		cin>>m;
		x.push_back(m); 
	}
}
int main()
{
	//freopen("input.in","r",stdin);
	//freopen("output.out","w",stdout);
	cin>>n;
	int m;
	for (int i=1;i<=n;i++)
	{
		cin>>m;
		a.push_back(m); 
	}
	for (int i=1;i<=n;i++)
	{
		cin>>m;
		b.push_back(m); 
	}
	for (int i=1;i<=n;i++)
	{
		cin>>m;
		c.push_back(m); 
	}
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	sort(c.begin(),c.end());
	ll ans=0;
	for (int i=0;i<b.size();i++)
	{
		int x=lower_bound(a.begin(),a.end(),b[i])-a.begin();
		int y=upper_bound(c.begin(),c.end(),b[i])-c.begin();
		y=c.size()-y;
		ans+=ll(x)*y;
	}
	cout<<ans;
	return 0;
}

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;
    cin >> N;
    
    vector<int> L;
    L.emplace_back(0);
    for (int i = 0; i < N; ++i) {
        int t;
        cin >> t;
        L.emplace_back(t);
    }
    L.emplace_back(0);
    int p = 0;
    int cost = 0;
    for (int j = 1; j < N+2; ++j) {
        cost += abs(L[j] - p);
        p = L[j];
    }
    
    for (int i = 1; i < N+1; ++i) {
        if ((L[i-1] < L[i] && L[i] < L[i+1]) || (L[i-1] > L[i] && L[i] > L[i+1])) {
            cout << cost << endl;
        } else {
            cout << cost - abs(L[i-1]-L[i]) - abs(L[i]-L[i+1]) + abs(L[i-1]-L[i+1]) << endl;
        }
    }
    
    
    return 0;
}

Measured memory_bytes: 1784
from collections import deque
n,m = map(int,input().split())
graph = [[] for _ in range(n)]
deg = [0]*n
seen = [False]*n
for i in range(m):
    x,y = map(int,input().split())
    graph[x-1] += [y-1]
    graph[y-1] += [x-1]
    deg[x-1] += 1
    deg[y-1] += 1
q = deque([i for i in range(n) if deg[i] == 1])
while q:
    v = q.popleft()
    seen[v] = True
    for i in graph[v]:
        deg[i] -= 1
        if deg[i] == 1:
            q.append(i)
if all(seen[i] == 1 for i in range(n)):print(n-1);exit()
print(seen.count(1))

Measured memory_bytes: 3316
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template<u32 M = 1000000007>
struct modint{
    u32 val;
    modint(): val(0){}
    template<typename T>
    modint(T t){t %= (T)M; if(t < 0) t += (T)M; val = t;}

    modint pow(ll k) const {
        modint res(1), x(val);
        while(k){
            if(k&1) res *= x;
            x *= x;
            k >>= 1;
        }
        return res;
    }
    template<typename T>
    modint& operator=(T t){t %= (T)M; if(t < 0) t += (T)M; val = t; return *this;}
    modint inv() const {return pow(M-2);}
    modint& operator+=(modint a){val += a.val; if(val >= M) val -= M; return *this;}
    modint& operator-=(modint a){if(val < a.val) val += M-a.val; else val -= a.val; return *this;}
    modint& operator*=(modint a){val = (u64)val*a.val%M; return *this;}
    modint& operator/=(modint a){return (*this) *= a.inv();}
    modint operator+(modint a) const {return modint(val) +=a;}
    modint operator-(modint a) const {return modint(val) -=a;}
    modint operator*(modint a) const {return modint(val) *=a;}
    modint operator/(modint a) const {return modint(val) /=a;}
    modint operator-(){return modint(M-val);}
    bool operator==(const modint a) const {return val == a.val;}
    bool operator!=(const modint a) const {return val != a.val;}
    bool operator<(const modint a) const {return val < a.val;}
};
using mint = modint<MOD>;

int main() {
    int n, k;
    cin >> n >> k;
    n++;
    mint ans = 0;
    vector<mint> v(n+1);
    for (int i = 0; i < n; ++i) {
        v[i+1] = v[i] + mint(i);
    }
    for (int i = k; i <= n; ++i) {
        mint l = v[i]-mint(1), r = v[n]-v[n-i];
        ans += r-l;
    }
    cout << ans.val << "\n";
    return 0;
}

Measured memory_bytes: 4052
// #pragma GCC target("avx2")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
 	if(a<b||b<0)return 0;
 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
long long pw(long long a,long long b){
	if(a<0LL)return 0;
	if(b<0LL)return 0;
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
// ここから編集しろ
char in[40][40];
int H,W,K;
char tmp[40][40];
int calc(int a,int b){
	for(int i=0;i<H;i++)for(int j=0;j<W;j++)tmp[i][j]=in[i][j];
	for(int i=a;i>0;i--){
		tmp[i][b]=tmp[i-1][b];
	}
	int ret=0;
	tmp[0][b]=0;
	int ks=1;
	while(1){
		int sum=0;
		for(int i=0;i<H;i++){
			int ren=0;
			for(int j=0;j<W;j++){
				if(tmp[i][j]==0){
					if(ren>=K){
						sum+=ren*(tmp[i][j-1]-'0');
						for(int k=1;k<=ren;k++)tmp[i][j-k]=0;
					}
					ren=0;
				}
				else if(j&&tmp[i][j]!=tmp[i][j-1]){
					if(ren>=K){
						sum+=ren*(tmp[i][j-1]-'0');
						for(int k=1;k<=ren;k++)tmp[i][j-k]=0;
					}
					ren=1;
				}else{
					ren++;
				}

			}
			if(ren>=K){
				sum+=ren*(tmp[i][W-1]-'0');
				for(int k=1;k<=ren;k++)tmp[i][W-k]=0;
			}
		}
		if(sum==0)break;
		ret+=sum*ks;
		ks*=2;
		for(int i=0;i<W;i++){
			int fa=H-1;
			for(int j=H-1;j>=0;j--){
				if(tmp[j][i]){
					tmp[fa--][i]=tmp[j][i];
				}
			}
			while(fa>=0){tmp[fa][i]=0;fa--;}
		}
	}
	return ret;
}
int main(){
	int a,b,c;scanf("%d%d%d",&a,&b,&c);H=a;W=b;K=c;
	for(int i=0;i<a;i++)scanf("%s",in[i]);
	int ret=0;
	for(int i=0;i<a;i++)for(int j=0;j<b;j++){
		ret=max(ret,calc(i,j));
	}
	printf("%d\n",ret);
}


Measured memory_bytes: 128
#include <algorithm>
#include <assert.h>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <functional>
#include <numeric>

using namespace std;
using lint = int64_t;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (lint i = 1; i < (n); ++i)
#define repn(i, a, b) for(lint i = (a); i < (b); ++i)
#define rep_inv(i, n) for (lint i = (n); i >= 0; --i)
#define all(vec) vec.begin(), vec.end()
#define cend printf("\n")

//constexpr lint mod = 998'244'353LL;
constexpr lint Mod = 1000'000'007LL;
constexpr lint Inf = 3'000'000'000'000'000'007LL; //3e18+7
constexpr double Pi = 3.141592653589793;

template<class T> using prique     = priority_queue<T>;
template<class T> using prique_inv = priority_queue<T, vector<T>, greater<T>>;
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& rhs) { return is >> rhs.first >> rhs.second; }
template<class T, class U>inline ostream& operator<<(ostream& os, const pair<T, U>& rhs) { return os << rhs.first << " " << rhs.second; }
template<class InputIterator> void arrin(InputIterator first, InputIterator last) { for (; first != last; ++first) cin >> (*first); }
template<class InputIterator> void arrout(InputIterator first, InputIterator last) {
	for (; first != last; ++first) {
		cout << (*first) << ((first + 1) != last ? " " : "\n");
	}
}

bool pri(lint x) { 
	for (lint i = 2; i * i <= x; ++i) {
		if (x % i == 0) return false;
	}
	return 1 < x; 
}

lint fact[3000000];
void fact_init(lint n, lint m = Mod) {
	if (3000000 <= n) return;
	fact[0] = fact[1] = 1;
	for (lint i = 2; i <= n; ++i) {
		fact[i] = i * fact[i - 1] % m;
	}
}

lint modpow(lint x, lint n, lint m = Mod) {
	lint res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % m;
		x = x * x % m;
		n >>= 1;
	}
	return res;
}

lint intpow(lint x, lint n) {
	lint res = 1;
	while (n > 0) {
		if (n & 1) res *= x;
		x *= x;
		n >>= 1;
	}
	return res;
}

lint comb(lint n, lint r, lint m = Mod) {
	if (r == 0 || r == n) return 1;
	lint res = fact[n] * modpow(fact[n - r], m - 2, m) % m * modpow(fact[r], m - 2, m) % m;
	return res < 0 ? res + m : res;
}

map<lint, lint> factring(lint n) {
	map<lint, lint> res;
	for (lint i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			n /= i;
			++res[i];
		}
	}
	if (n != 1) ++res[n];
	return res;
}

int main() {
	int x;
	cin >> x;
	if (30 <= x) cout << "Yes\n";
	else cout << "No\n";
}

Measured memory_bytes: 3628
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<cmath>
#include<string>

#define ls (t<<1)
#define rs ((t<<1)+1)
#define mid ((l+r)>>1)
#define fi first
#define se second
#define mk make_pair
#define pb push_back

#define N 105
#define M 200005
#define seed 23333
#define Mo 998244353

using namespace std;
int i,j,m,n,p,k,sx,sy,l,sum[N][N];
short int f[N][N][N][N];
char c[N][N];
int Sum(int sx,int ex,int sy,int ey)
{
		return sum[ex][ey]-sum[sx-1][ey]-sum[ex][sy-1]+sum[sx-1][sy-1];
}
void Max(short int &x,short int y)
{
		if (x<y) x=y;
}
int main()
{
	 scanf("%d%d",&n,&m);
	 for (i=1;i<=n;++i) 
	 {
	 	scanf("%s",c[i]+1);
	 	for (j=1;j<=m;++j) if (c[i][j]=='E') sx=i,sy=j;
	 }
	 for (i=1;i<=n;++i)
	 		for (j=1;j<=m;++j)
			 	sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(c[i][j]=='o'); 
	 for (i=1;i<=n;++i)
	 	for (j=i;j<=n;++j)
		 	for (k=1;k<=m;++k)
			 	for (l=k;l<=m;++l)
				 	f[i][j][k][l]=-10000;
	 f[1][n][1][m]=0;
	 for (i=1;i<=n;++i)
	 	for (j=n;j>=i;--j)
		 	for (k=1;k<=m;++k)
			 	for (l=m;l>=k;--l)
				 	if (f[i][j][k][l]>=0)
					{
							int gg=0; 
							//up
							if (i<j)
							{
									gg=sx+i;
									if (gg>=i&&gg<=j)
									{ 
										int str=max(k,sy-(m-l)),end=min(l,sy+k-1);
										Max(f[i+1][j][k][l],Sum(gg,gg,str,end)+f[i][j][k][l]);
									}
							}
							//down
							if (i<j)
							{
									gg=sx-(n-j)-1;
									if (gg>=i&&gg<=j)
									{
										int str=max(k,sy-(m-l)),end=min(l,sy+k-1);
										Max(f[i][j-1][k][l],Sum(gg,gg,str,end)+f[i][j][k][l]);
									}
							}
							//left
							if (k<l)
							{
									gg=sy+k;
									if (gg>=k&&gg<=l)
									{
										int str=max(i,sx-(n-j)),end=min(j,sx+i-1);
										Max(f[i][j][k+1][l],Sum(str,end,gg,gg)+f[i][j][k][l]);
									}
							}
							//right
							if (k<l)
							{
									gg=sy-(m-l)-1;
									if (gg>=k&&gg<=l)
									{
										int str=max(i,sx-(n-j)),end=min(j,sx+i-1);
										Max(f[i][j][k][l-1],Sum(str,end,gg,gg)+f[i][j][k][l]);
									}
							}
					}
	short int ans=0;
	 for (i=1;i<=n;++i)
	 	for (j=n;j>=i;--j)
		 	for (k=1;k<=m;++k)
			 	for (l=m;l>=k;--l)
			 		Max(ans,f[i][j][k][l]);
	cout<<ans<<endl;
}


Measured memory_bytes: 109312
#include <bits/stdc++.h>
using namespace std;
	
int main(){
  int i,j,k,l;
  int N;
  cin>>N;
  long long a[N+1];
  int x;
  cin>>a[0];
  for(i=1;i<N;i++) {
	cin>>x;
	a[i]=a[i-1]+x;
  }
  a[N]=0;
  sort(a,a+N+1);
  long long ans=0;
  j=1;
  long long pre=a[0];
  long long count=1;
  while(j<=N){
	if(a[j]!=pre){
		pre=a[j];
		ans+=count*(count-1)/2;
		count=1;
	}
	else count+=1;
	j+=1;
  }
  ans+=count*(count-1)/2;
  cout<<ans<<endl;
  return 0;
}


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

void solve() {
  priority_queue<int> q;
  int n, m;
  cin >> n >> m;
  vector<vector<int>> v(m+1);
  int a, b;
  rep(i, n) {
    cin >> a >> b;
    if (a < m + 1) {
      v[a].push_back(b);
    }
  }
  ll ans = 0;
  for (int i = 0; i <= m; ++i) {
    if (v[i].empty()) {
      q.push(0);
    } else {
      for (int j: v[i]) q.push(j);
    }
    ans += q.top();
    q.pop();
  }

  cout << ans << endl;
}

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


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

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

void no(){
	cout<<"No"<<endl;
	exit(0);
}
void yes(){
	cout<<"Yes"<<endl;
	exit(0);
}

//KUPC2017J
//AOJDSL1A
//without rank
struct unionfind{
	vi p,s;
	int c;
	unionfind(int n):p(n,-1),s(n,1),c(n){}
	int find(int a){
		return p[a]==-1?a:(p[a]=find(p[a]));
	}
	//set b to a child of a
	bool unite(int a,int b){
		a=find(a);
		b=find(b);
		if(a==b)return false;
		p[b]=a;
		s[a]+=s[b];
		c--;
		return true;
	}
	bool same(int a,int b){
		return find(a)==find(b);
	}
	int sz(int a){
		return s[find(a)];
	}
};

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	int n,m,q;cin>>n>>m>>q;
	
	vc<pi> dup;
	unionfind uf(n);
	rep(_,q){
		int u,v,f;cin>>u>>v>>f;
		if(f==0)
			uf.unite(u,v);
		else
			dup.eb(u,v);
	}
	
	if(m==n-1){
		if(dup.size())no();
		yes();
	}
	
	for(auto e:dup)
		if(uf.same(e.a,e.b))no();
	
	if(m<=n-uf.c+uf.c*(uf.c-1)/2)yes();
	else no();
}

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

#ifdef LOCAL
#define debug(var) cerr << (#var) << " = " << (var) << endl;
#else
#define debug(var)
#endif

void init() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}

const int N = 2e5+34;

long long a[N];
long long b[N];

void solve() {
  int n; scanf("%d", &n);
  long long tot = 0;
  for (int i = 0; i < n; ++i) {
    scanf("%lld", a+i);
    a[i] -= (i+1);
  }
  sort(a, a+n);
  b[0] = a[0];
  for (int i = 1; i < n; ++i) b[i] += b[i-1]+a[i];
  long long ans = 1e15;
  for (int i = 0; i < n; ++i) {
    ans = min(ans, a[i]*(2*i+2-n)-2*b[i]+b[n-1]);
  }
  printf("%lld", ans);
}

int main() {
  int t = 1; //scanf("%d", &t);
  while (t--) {
    solve();
  }
  return 0;
}


Measured memory_bytes: 3328