akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
using namespace std;

int main()
{
  int n,ans=0;
  vector<int> all;
  cin>>n;
  for(int i = 0;i<n;i++)
  {
    int tmp;
    cin>>tmp;
    all.push_back(tmp);
  }
  for(int i=1;i<n-1;i++)
  {
    if(all.at(i)>all.at(i-1)&&all.at(i)<all.at(i+1))
      ans++;
     else if(all.at(i)<all.at(i-1)&&all.at(i)>all.at(i+1))
       ans++;
      else
        continue;
  }
  cout<<ans<<endl;
  return 0;
}

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

int main(){
	ios::sync_with_stdio(0);
	cout << setprecision(10) << fixed;
	int n;
	cin >> n;
	vector<int> a(n);
	int mi = 1e9 + 1, mx = 0;
	for (int i = 0; i < n; ++i){
		cin >> a[i];
		mi = min(mi, a[i]);
		mx = max(mx, a[i]);
	}
	int ans = 1e9 + 1;
	for (int i = mi; i <= mx; ++i){
		int temp = 0;
		for (int j = 0; j < n; ++j){
			temp += pow(abs(i - a[j]), 2);
		}
		ans = min(temp, ans);
	}
	cout << ans;
	return 0;
}



Measured memory_bytes: 256
#pragma region
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define repc(i, m, n) for (int i = m; i < n; i++)
#define reprc(i, m, n) for (int i = m; i > n; i--)
#define all(v) v.begin(), v.end()
#define INF 1e9
#define EPS 1e-10
using namespace std;
typedef long long ll;
#pragma endregion

int main()
{
    ll N,c = 0;
    cin >> N;

    repc(i, 1, N + 1){
        if(i % 3 != 0 && i % 5 != 0){
            c += i;
        }
    }

    cout << c << endl;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define repr(i,x,n) for(int i=x; i<(n); i++)
#define ALL(x) (x).begin(),(x).end()
#define INF 1e9
typedef long long ll;
using VI = vector<int>;
using VB = vector<bool>;
using VS = vector<string>;
using graph = vector<vector<int>>;

int main()
{
ll n,d,ans=0,a,b;

cin>>n>>d;
VI x(n);
VI y(n);
for (int i = 0; i < n; i++)
{
cin>>x.at(i)>>y.at(i);
if (pow(pow(x.at(i),2.0)+pow(y.at(i),2),0.5)<=d)
{
    ans++;
}


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

Measured memory_bytes: 4836
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
using namespace std;
typedef long long ll;
typedef long long int llint;
typedef pair<ll, ll> pa;
#define MM 1000000000
#define MOD MM+7
#define MAX 101000
#define MAP 110
#define initial_value -1
#define MAX_T 1001
#define Pair pair<int,int>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define INF (1 << 29) //536870912
const long double PI = acos(-1);
const ll DEP = 1e18;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
void init(int a[100001]){
    for(int i = 0; i < 100001; i++){
        a[i] = MM;
    }
}
int main(){
    int N,K; cin >> N >> K;
    int h[100001];
    for(int i = 0; i < N; i++) cin >> h[i];
    int dp[1000001];
    init(dp);
    dp[0] = 0; dp[1] = abs(h[1]-h[0]);
    for(int i = 0; i < N; i++){
        for(int j = 1; j <= K && i+j < N; j++){
            dp[i+j] = min(dp[i+j],dp[i] + abs(h[i+j]-h[i]));
        }
    }
    cout << dp[N-1] << endl;
}


Measured memory_bytes: 3072
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;

int main(){
    int N, T;
    cin >> N >> T;
    int c, t, ans = INT_MAX;
    REP(i, N){
        cin >> c >> t;
        if(t <= T && c <= ans) ans = c;
    }
    if(ans == INT_MAX) cout << "TLE" << endl;
    else cout << ans << endl;
    return 0;
}



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

// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds; 
  
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
 
#define FS              ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll              long long int
#define ld              long double
#define pb              push_back
#define bp              __builtin_popcount
#define sz              size()
#define ff              first
#define ss              second
#define vll             vector<ll>
#define vbool           vector<bool>
#define vpll            vector<pair<ll,ll>>
#define pll             pair<ll,ll>
#define vllv            vector<vector<ll>>
#define setpri(x)       cout<<setprecision(x)<<fixed;
#define all(v)          v.begin(),v.end()
#define allr(v)         v.rbegin(),v.rend()
#define yesr {cout<<"YES"<<endl;return;}
#define nor {cout<<"NO"<<endl;return;}
// getline (std::cin,name);
ll MOD=1e9+7;
ll ceil1(ll n,ll x){return (n-1)/x+(n>0);}

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

ll pow1(ll n,ll m ,ll mod=MOD );
ll pow2(ll n,ll k);

ll modinv(ll n,ll mod=MOD){  return pow1(n,mod-2,mod);}

bool func(pair<ll,ll> &a,pair<ll,ll> &b ){
        if(a.ff != b.ff)return a.ff < b.ff;
        return a.ss > b.ss;
}

ll const N=(ll)2e5+11;
ll const LG=(ll)log2(N)+1;


void solve(){
        ll i,j,k,l,n,m,x,y,z,r;
       
       string s;
       cin>>s;
       n=s.sz;
       ll a1,a2;
       a1=0,a2=0;
       for(i=0;i<n;i++){
               int a=s[i]-'0';
               if(a%2!=i%2){
                       a1++;
               }else{
                       a2++;
               }
       }
       cout<<min(a1,a2)<<endl;
       
       
        
}       
int main(){
        FS;
        
        ll i,j,k,n,m,x,y,z,q;
        q=1;
        // cin>>q;
        for(ll tc=1;tc<=q;tc++){
                // cout<<"Case #"<<tc<<": ";
                solve();
        }
        return 0;
}


ll pow1(ll n,ll m,ll mod){
        if(m==0)return 1;
        
        if(m%2==0)return pow1((n*n)%mod,m/2,mod);
    	
    	return (pow1((n*n)%mod,m/2,mod)*n)%mod;
}

ll pow2(ll n,ll k){
        ll ans=1;
            while(k>0){
                if(k%2==1)ans=ans*n;
                n=n*n;
                k/=2;
            }
            return ans;
}


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

#define int long long

template<class T>void chmod(T &a, const T &b, const T &mod) {
  int val = (a % mod) + (b % mod);
  if (val < 0) { val += mod; }
  a = val;
}

const int MOD = 1e9 + 7;
string K;
int D;

int dp[10010][2][110] = {0};

signed main() {
  cin >> K >> D;
  int n = K.size();

  dp[0][0][0] = 1;
  for (int digit = 0; digit < n; digit++) { // 上からdigit桁目
    for (int smaller : {0, 1}) {
      int lim = smaller == 1 ? 9 : K[digit] - '0'; // この桁の上限値
      for (int num = 0; num <= lim; num++) {
        for (int modD = 0; modD < D; modD++) {
          chmod(dp[digit+1][smaller || num < lim][(modD + num) % D], dp[digit][smaller][modD], MOD);
        }
      }
    }
  }

  int ans = 0;
  for (int smaller : {0, 1}) {
    chmod(ans, dp[n][smaller][0], MOD);
  }
  chmod(ans, -1LL, MOD);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 17408
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<complex>
#define rep(i, a, n) for(int i=a;i<n;i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define R long double 
#define P complex<R>
using namespace std;
const int mod = 1000000007;
const int INF = 1e12;
template<class T>bool chmax(T &a, const T &b) { return (a < b) ? (a = b, 1) : 0;}
template<class T>bool chmin(T &a, const T &b) { return (b < a) ? (a = b, 1) : 0;}
const R PI = acos(-1.0L);
const R inf = 1e13;
int x[110], y[110];
R ans[110];
inline R dist(int i, P q) {
   P p = P(x[i], y[i]);
   return norm(p - q);
}
signed main(){
    int n;
    cin>>n;
    for (int i=0;i<n;i++)
	{
		cin>>x[i]>>y[i];
    }
    int limit = 200000;
    rep(i, 0, limit){
        R cur = 2.0 * PI / limit * i;
        P point = polar(inf, cur);
        R d = 1e130;
        int idx = -1;
        rep(j, 0, n) if(chmin(d, dist(j, point))) idx = j;
        ans[idx] += 1.0;
    }
    cout.precision(20);
	rep(i, 0, n) cout << fixed << 1.0 * ans[i] / limit << endl;
	return 0;
}



Measured memory_bytes: 768
h,w=map(int,input().split())
M=[input() for _ in range(h)]

L=[[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if M[i][j]=='#':
            L[i][j]=0
        elif j!=0:
            L[i][j]=L[i][j-1]+1
        else:
            L[i][j]=1
    
R=[[0]*w for _ in range(h)]
for i in range(h):
    for j in reversed(range(w)):
        if M[i][j]=='#':
            R[i][j]=0
        elif j!=w-1:
            R[i][j]=R[i][j+1]+1
        else:
            R[i][j]=1

U=[[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if M[i][j]=='#':
            U[i][j]=0
        elif i!=0:
            U[i][j]=U[i-1][j]+1
        else:
            U[i][j]=1

D=[[0]*w for _ in range(h)]
for i in reversed(range(h)):
    for j in range(w):
        if M[i][j]=='#':
            D[i][j]=0
        elif i!=h-1:
            D[i][j]=D[i+1][j]+1
        else:
            D[i][j]=1

ans=1
for i in range(h):
    for j in range(w):
        if M[i][j]=='#':
            continue
        ans=max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
print(ans)

Measured memory_bytes: 181764
//1.read question_2.read I/O_3.read test cases_4.read constraints(to decide TC of solution)_5.decide method_6.dry run_
//7.code_8.test_9.submit
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define mod 1000000007
#define F first
#define S second
#define _READ freopen("input.txt","r", stdin);
#define pb push_back
#define MP make_pair
#define _FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int main()
{
   
    lli n,m;
    cin>>n>>m;
    cout<<ceil(1.0*n/m);
    return 0;
}


Measured memory_bytes: 256
#if 0

#endif

#include <algorithm>
#include <iostream>
using namespace std;

int T,N,K,X[100000+10],A[100000+10];
int main(){
	cin >> T;
	for(int t=0; t<T; ++t){
		int tot=0;
		cin >> N >> K;
		for(int i=0; i<N; ++i) cin >> X[i];
		for(int i=0; i+1<N; ++i) A[i]=X[i+1]-X[i]; //??????????????\??£?????????(size:N-1)
		sort(A,A+N-1); //????????????????????????
		if(N>=K){ //??¶?????°>=?????????
			for (int i=0; i<(N-1)-(K-1); ++i) tot += A[i];
			cout << tot << endl;
		}
		else
			cout << 0 << endl;
	}
	return 0;
}

Measured memory_bytes: 3780
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<sstream>
#include<cstdlib>

using namespace std;
 
typedef long long ll;
  
ll expression();
ll term();
ll factor();
ll number();
  
int now;
string s;
ll P;
bool fg;
 
ll extgcd(ll a, ll b, ll& x, ll& y){
  ll d = a;
  if(b!=0){
    d=extgcd(b, a%b ,y,x);
    y-=(a/b)*x;
  }
  else{
    x=1; y=0;
  }
  return d;
}
 
ll mod_inverse(ll a,ll m){
  ll x,y;
  extgcd(a,m,x,y);
  return (m+x%m)%m;
}
 
ll expression(){
  if(fg)return 0;
    ll res=term();
        while(true){
      if(s[now]=='+')now++,(res+=term())%=P;
      else if(s[now]=='-')now++,(res+=P-term())%=P;
      else break;
    }
    return res;
}
 
ll term(){
  ll res=factor();
  while(true){
    if(s[now]=='(')res+=factor();
    else if(s[now]=='*')now++,(res*=factor())%=P;
    else if(s[now]=='/'){
      now++;
      ll tmp=factor();
      if(tmp==0)fg=true;
      res=((res%P)*mod_inverse(tmp,P)%P)%P;
    }
    else break;
  }
  return res;
}
 
ll factor(){
    ll res=0;
    if(s[now]=='('){
        now++;
        res=expression()%P;
        now++;
    }
    else return number();
      
    return res%P;
}
  
ll number(){
    ll res=0;
    while('0'<=s[now] && s[now]<='9'){
        res*=10;
        res+=s[now++]-'0';
    }
    return res%P;
}
 
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

int main(){
  string tmp;
  while(getline(cin,tmp)){
    if(tmp[0] == '0')break;

    for(int i=0;i<tmp.size();i++){
      if(tmp[i]==':'){
	tmp[i]=' ';
	break;
      }
    }

    now = 0;
    s.clear();
    stringstream ss;
    ss << tmp;
    ss >> tmp;
    P = (atol)(tmp.c_str());
    while(!(ss >> tmp).fail()){
      s += tmp;
    }
 
    fg = false;
    ll ans = expression();
    if(fg) cout << "NG" << endl;
    else  cout << s << " = " << ans << " (mod " << P << ")" << endl;
 
  }
 
  return 0;
}

Measured memory_bytes: 1560
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>

using namespace std;
int rate[9];
int n,tmp,syou,ans,ma,mi;

int main()
{
	cin >> n;
	for(int i = 0;i < n;i++)
	{
		cin >> tmp;
		syou = tmp / 400;
		if(syou < 8)
			rate[syou]++;
		else
			rate[8]++;
	}
	
	for(int i = 0;i < 8;i++)
		if(rate[i])ans++;
	if(!ans)
	{
		ans++;
		rate[8]--;
	}

	cout << ans << " " << ans + rate[8] << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
	int n;
	int a[3000];

	cin >> n;

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

	int sum = 0;
	for(int i = 0; i < n; ++i)
	{
		sum += a[i] - 1;
	}

	cout << sum << endl;
}

Measured memory_bytes: 256
n,l=map(int, input().split())
t=0
c=0
for i in range(n):
  if i==0:
    t=abs(l+(i+1)-1)
    c=i+1
  else:
    t=min(t, abs(l+(i+1)-1))
    if t==abs(l+(i+1)-1):
      c=i+1
#print(c)
g=0
for i in range(n):
  g+=(l+(i+1)-1)
#print(g)
print(g-l-c+1)


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

using namespace std;

#define ll long long

const int N = 2e5+15;

vector<int> d[N];

int mini[N];

set<int> mm[N];

void solve(){
	int h,w,n;
	scanf("%d%d%d",&h,&w,&n);
	set<pair<int,int> >s;
	for(int y=1;y<=w;++y){
		mini[y] = h;
	}
	for(int i=0;i<n;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		if(s.count(make_pair(x,y))){
			continue;
		}
		s.insert(make_pair(x,y));
		mm[y].insert(x);
		mini[y] = min(mini[y],x);
	}
	int ret = h;
	int y = 1;
	for(int x=1;x<=h;++x){
		while(mm[y].size()>0){
			if( *(mm[y].begin())<=x){
				if(*mm[y].begin() == x){
					ret = min(ret,x);
					break;
				}
				mm[y].erase(mm[y].begin());
			} else {
				break;
			}
		}
		//cout<<x<<" "<<y<<endl;
		if(mm[y].size()>0){
			ret = min(ret, *mm[y].begin() -  1);
		}
		if(y+1<=x && !s.count(make_pair(x,y+1))){
			++y;
		}
	}
	printf("%d\n", ret);

}
int main(){
	//freopen("input.txt","r",stdin);
	solve();
}

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

int main() {
    double W, H, x, y;
    cin >> W >> H >> x >> y;

    printf("%lf ", W*H/2);

    if((x == W/2) && (y == H/2)){
        cout << 1;
    } else {
        cout << 0;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;
#define int long long


void solve(long long N, long long D, std::vector<std::vector<long long>> X){
    int res = 0;
    for(int i = 0; i < N; ++i) {
        for(int j = i + 1; j < N; ++j) {
            int a = 0;
            for(int k = 0; k < D; ++k) {
                a += (X[j][k] - X[i][k]) * (X[j][k] - X[i][k]);
            }

            for(int k = 0; k * k <= a; ++k) {
                if (k * k == a) {
                    res++;
                }
            }
        }
    }
    cout << res << endl;
}

signed main(){
    long long N;
    scanf("%lld",&N);
    long long D;
    scanf("%lld",&D);
    std::vector<std::vector<long long>> X(N, std::vector<long long>(D));
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < D ; j++){
            scanf("%lld",&X[i][j]);
        }
    }
    solve(N, D, std::move(X));
    return 0;
}


Measured memory_bytes: 256
def f(n):
    if n % 2 == 0:
        return n // 2
    else:
        return 3 * n + 1


def main():
    a = int(input())
    a_dict = {a: 1}

    for i in range(2, 1000001):
        a = f(a)
        if a not in a_dict:
            a_dict[a] = 1
        else:
            print(i)
            break


if __name__ == "__main__":
    main()


Measured memory_bytes: 61892
N = input()
A, B, C, D = int(N[0]), int(N[1]), int(N[2]), int(N[3])
OP = ["+", "-"]

ANS = 0
flg = False


for op1 in OP:
    if flg is True:
        break
    ANS = A
    if op1 == "+":
        ANS = ANS + B
    else:
        ANS = ANS - B
    for op2 in OP:
        if flg is True:
            break
        ANS2 = ANS
        if op2 == "+":
            ANS2 = ANS + C
        else:
            ANS2 = ANS - C
        for op3 in OP:
            ANS3 = ANS2
            if op3 == "+":
                ANS3 = ANS2 + D
            else:
                ANS3 = ANS2 - D
            if ANS3 == 7:
                print("%d%s%d%s%d%s%d=7" % (A, op1, B, op2, C, op3, D))
                flg = True
                break


Measured memory_bytes: 3064
#include <stdio.h>
#include <string.h>
int main ()
{
	int a,b,c,d,i;
	char s[107];
	scanf ("%s",s);
    a=strlen(s);
	for (i=0;i<a;i++)
	{
		printf ("x");
	}
	printf ("\n");
	return 0;
}

Measured memory_bytes: 128
import sys
import math
import bisect

def solve(s):
    n = len(s)
    max_val = 0
    for i in range(1, n):
        s1 = set(list(s[0:i]))
        s2 = set(list(s[i:]))
        val = len(s1 & s2)
        max_val = max(max_val, val)
    return max_val

def main():
    n = int(input())
    s = input()
    print(solve(s))

if __name__ == "__main__":
    main()


Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
int n, a, b;
int h[maxn];
bool check(ll mid)
{
	ll ret = 0;
	for(int i = 1; i <= n; ++i)
	{
		if(h[i] <= mid * b) continue;
		ret += (h[i] - mid * b + a - 1) / a;
	}
	return ret <= mid;
}	
int main()
{
	scanf("%d%d%d", &n, &a, &b);
	a -= b;
	for(int i = 1; i <= n; ++i) scanf("%d", &h[i]);
	int l = 1, r = 1e9;
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(check(mid))
			r = mid - 1;
		else
			l = mid + 1;
	}
	cout << l << endl;
	return 0;
}

Measured memory_bytes: 4120
H,W = map(int,input().split())
char = [0 for _ in range(26)]
rem = [0,0,0,0]

for i in range(H):
    a = input()
    for j in range(W):
        char[ord(a[j])-97] += 1

for i in range(26):
    rem[char[i]%4] += 1
    
if H%2==0 and W%2==0:
    print('Yes' if rem[0]==26 else 'No')
    
elif H%2!=0 and W%2!=0:
    print('Yes' if rem[1]+rem[3]==1 and rem[2]+rem[3]<=(H-1)//2+(W-1)//2 else 'No')
    
else:
    print('Yes' if rem[1]+rem[3]==0 and rem[2]<=(H%2)*(W//2)+(W%2)*(H//2) else 'No')


Measured memory_bytes: 38896
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#define dlog(str) cout << "====" << str << endl;
#else
#define dlog(str)
#endif
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
#define FOR(i, s, e) for(int i = s, i##_l = (e); i < i##_l; i++)
#define LLI long long int
#define _min(a,b) ((a<b)?a:b)
#define _max(a,b) ((a<b)?b:a)
#define chmax(a, b) a = _max(a, b)
#define chmin(a, b) a = _min(a, b)
#define bit(a, shift) ((a>>shift)&1))
#define pm(a) ((a)?1:-1)
#define SORT(v) sort(v.begin(),v.end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
// int 2.14E±9    lli 9.2E±18    double 1.7E±380


int main()
{
    cout << fixed << setprecision(10);
    int k,x;
    cin >> k>>x;
    if (x <= 500 * k)
        cout << "Yes";
    else cout << "No";
    return 0;
}

Measured memory_bytes: 256
fn main() {
	let mut s = String::new();
	use std::io::Read;
	std::io::stdin().read_to_string(&mut s).unwrap();
	let mut s = s.split_whitespace();
	let n: usize = s.next().unwrap().parse().unwrap();
	use std::cmp::Reverse;
	let mut dp = vec![Reverse(-1); n];
	for a in s.take(n).map(|a| a.parse::<i32>().unwrap()) {
		let i = dp.upper_bound(&Reverse(a));
		dp[i] = Reverse(a);
	}
	println!("{}", dp.upper_bound(&Reverse(0)));
}

pub trait BinarySearch<'a, T: 'a> {
	fn upper_bound(&self, x: &T) -> usize;
}

impl<'a, T: 'a + Ord> BinarySearch<'a, T> for [T] {
	fn upper_bound(&self, x: &T) -> usize {
		let mut first = 0;
		let mut len = self.len() - first;
		while len > 0 {
			let half = len >> 1;
			let mid = first + half;
			use std::cmp::Ordering;
			match x.cmp(&self[mid]) {
				Ordering::Less => {
					len = half;
				}
				Ordering::Equal | Ordering::Greater => {
					first = mid + 1;
					len = len - half - 1;
				}
			}
		}
		first
	}
}


Measured memory_bytes: 3464
#include <stdio.h>
#include <algorithm>

using namespace std;

typedef long long ll;

#define N 110000

int n, m, tot, k;
ll a[N], b[N], pre1[N], pre2[N];
ll sum = 11111111111111111, cnt = 0;

int cmp(ll a, ll b) {
    return a > b;
}

int main() {
    n = m = 1;
    scanf("%d%d", &tot, &k);
    for (int i = 0; i < tot; ++i) {
        ll x; scanf("%lld", &x);
        if (!x) ++cnt;
        if (x < 0) a[n++] = -x;
        if (x > 0) b[m++] = x;
    }
    n--, m--;
    sort(a + 1, a + n + 1);
    if (cnt >= k) { puts("0"); return 0; }
    k -= cnt;
    for (int i = 0; i <= min(k, m); ++i){
        if (n < k - i) continue;
        sum = min(sum, min(b[i] * 2 + a[k - i], a[k - i] * 2 + b[i]));
    }
    printf("%lld\n", sum);
    return 0;
}


Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

using Pair = System.Collections.Generic.KeyValuePair<int, int>;

class Program
{
	public Program() { }

	static void Main(string[] args)
	{
		new Program().prog();
	}
	Scanner cin;
	const int MOD = 1000000007;
	const int INF = int.MaxValue;
	const double EPS = 1e-7;
	const double PI = 3.1415926536;

	void prog()
	{
		cin = new Scanner();
		int[,] dir8 = new int[8, 2] { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { 0, 1 }, { 1, -1 }, { 1, 0 }, { 1, 1 } };
		int[,] dir4 = new int[4, 2] { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };

		string s = cin.next();
		string ans = "";
		for (int i = 0; i < s.Length; i++)
		{
			if (s[i] == 'B')
			{
				if (ans.Length == 0) continue;
				ans = ans.Substring(0, ans.Length - 1);
			}
			else
			{
				ans += s[i];
			}
		}
		Console.WriteLine(ans);
	}
}

class Scanner
{
	string[] s;
	int i;

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

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

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

	public int nextInt()
	{
		return int.Parse(next());
	}

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

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

Measured memory_bytes: 2648
#include <cstdio>
#include <cstdlib>
#include <cstring>
 
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
 
using namespace std;

const int kMaxN = 310;

int a[kMaxN][kMaxN], pos[kMaxN][kMaxN], cnt[kMaxN], n, m;
set<pair<int, int> > s[kMaxN];

bool check(int mid)
{
	for (int i = 1; i <= n; i++)
	{
		s[i].clear();
		for (int j = 1; j <= m; j++)
			s[i].insert(make_pair(j, a[i][j]));
	}
	for (int k = 1; k < m; k++)
	{
		bool can = 1;
		memset(cnt, 0, sizeof cnt);
		for (int i = 1; i <= n; i++)
		{
			auto t = *s[i].begin();
			cnt[t.second]++;
		}
		int idx = -1;
		for (int i = 1; i < kMaxN; i++)
			if (cnt[i] > mid)
				can = 0, idx = i;
		if (can) return true;
		for (int i = 1; i <= n; i++)
			s[i].erase(make_pair(pos[i][idx], idx));
	}
	return false;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			cin >> a[i][j];
			pos[i][a[i][j]] = j;
		}
	int low = 0, high = n, ans = high;
	while (low <= high)
	{
		int mid = (low + high) / 2;
		if (check(mid))
			ans = mid, high = mid - 1;
		else
			low = mid + 1;
	}
	cout << ans << endl;
#ifdef GLOBAL_DEBUG
	system("pause");
#endif
	return 0;
}

Measured memory_bytes: 5248
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = input()
print("x"*len(S))


Measured memory_bytes: 6104
// Problem : A - Tenki
// Contest : AtCoder Beginner Contest 139
// URL : https://atcoder.jp/contests/abc139/tasks/abc139_a
// Memory Limit : 1024,000000 MB 
// Time Limit : 2000,000000 milisec 
// Powered by CP Editor (https://github.com/coder3101/cp-editor2)

#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main() {
#ifdef _DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif

  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cout.precision(16);
  cout << fixed;
  
  string s;
  string t;
  cin >> s >> t;
  
  int ans = 0;
  
  for (int i = 0; i < (int)s.size(); ++i) {
    if (s[i] == t[i])
      ++ans;
  }
  
  cout << ans;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys

sys.setrecursionlimit(100000)
# input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m


def slv(N, M, A):
    m = Mod(10**9 + 7)
    dp = [0] * (N+10)
    b = [False] * (N+10)
    for a in A:
        b[a] = True

    dp[0] = 1
    for i in range(N):
        if not b[i+1]:
            dp[i+1] = m.add(dp[i+1], dp[i])
        if not b[i+2]:
            dp[i+2] = m.add(dp[i+2], dp[i])
    return dp[N]


def main():
    N, M = read_int_n()
    A = [read_int() for _ in range(M)]
    print(slv(N, M, A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 9196
# A

N = int(input())
A = list(map(int, input().split()))

Acum = [0] + A
dic = {0: 1}
for i in range(1, N + 1):
    Acum[i] += Acum[i - 1]
    if Acum[i] in dic.keys():
        dic[Acum[i]] += 1
    else:
        dic[Acum[i]] = 1
ans = 0
for v in dic.values():
    if v > 1:
        ans += int(v * (v - 1) / 2)

print(ans)


Measured memory_bytes: 40396
#include<cstdio>

int main(){
	int h,w,n;
	scanf("%d%d%d",&h,&w,&n);
	int x[10000];
	int a[10000];
	int cur = 0;
	for(int i=0;i<n;i++){
		scanf("%d",a+i);
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<a[i];j++){
			x[cur] = i + 1;
			cur++;
		}
	}
	int c[100][100];
	for(int i=0;i<h*w;i++){
		int yoko = i / h;
		int tate = i % h;
		if(yoko%2==0){
			c[tate][yoko] = x[i];
		}else{
			c[h-1-tate][yoko] = x[i];
		}
	}
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			printf("%d",c[i][j]);
			if(j==w-1) printf("\n");
			else printf(" ");
		}
	}
}


Measured memory_bytes: 384
use std::cmp::{Ordering, max, min};
use std::io::{self, BufRead};
use std::collections::{BinaryHeap, HashMap, HashSet};

struct Vertex(usize, usize, usize);

impl Ord for Vertex {
  fn cmp(&self, other: &Self) -> Ordering {
    other.0.cmp(&self.0)
  }
}

impl PartialOrd for Vertex {
  fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
    Some(other.0.cmp(&self.0))
  }
}

impl PartialEq for Vertex {
  fn eq(&self, other: &Self) -> bool {
    self.0 == other.0
  }
}

impl Eq for Vertex {}

fn main() {
  let stdin = io::stdin();
  let mut lines = stdin.lock().lines();
  let line = lines.next().unwrap().unwrap();
  let vs: Vec<usize> = line.split(' ').map(|x| x.parse().unwrap()).collect();
  let (n, m, mut s) = (vs[0], vs[1], vs[2]);
  let mut rs: Vec<HashMap<usize, (usize, usize)>> = vec![HashMap::new(); n];
  let mut max_s = 0;
  for _ in 0..m {
    let line = lines.next().unwrap().unwrap();
    let vs: Vec<usize> = line.split(' ').map(|x| x.parse().unwrap()).collect();
    let u = vs[0] - 1;
    let v = vs[1] - 1;
    rs[u].insert(v, (vs[2], vs[3]));
    rs[v].insert(u, (vs[2], vs[3]));
    max_s = max(max_s, vs[2]);
  }
  max_s = (n - 1) * max_s;
  s = min(max_s, s);
  let mut xs: Vec<(usize, usize)> = Vec::new();
  for _ in 0..n {
    let line = lines.next().unwrap().unwrap();
    let vs: Vec<usize> = line.split(' ').map(|x| x.parse().unwrap()).collect();
    xs.push((vs[0], vs[1]));
  }

  let mut queue = BinaryHeap::new();
  queue.push(Vertex(0, 0, s));
  let mut fixed = HashSet::new();
  let mut ts = vec![vec![usize::max_value(); max_s+1]; n];
  ts[0][s] = 0;
  while let Some(Vertex(t, u, s)) = queue.pop() {
    if fixed.contains(&(u, s)) {
      continue;
    }
    fixed.insert((u, s));
    if s < max_s {
      let s1 = min(max_s, s+xs[u].0);
      let t1 = t + xs[u].1;
      queue.push(Vertex(t1, u, s1));
      ts[u][s1] = min(ts[u][s1], t1);
    }
    for (v, (a, b)) in &rs[u] {
      if *a <= s {
        let s1 = s - *a;
        let t0 = ts[*v][s1];
        let t1 = ts[u][s] + b;
        if t0 == usize::max_value() || t1 < t0 {
          ts[*v][s1] = t1;
        }
        if !fixed.contains(&(*v, s1)) {
          queue.push(Vertex(t1, *v, s1));
        }
      }
    }
  }
  for i in 1..n {
    println!("{}", ts[i].iter().cloned().min().unwrap());
  }
}

Measured memory_bytes: 13476
/*
    author: kartik8800
*/
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;

int solve(vector<int>& height, int n)
{
    vector<int> dp(n+1);
    dp[1] = 0;
    for(int i = 2; i <= n; i++)
    {
        if(i == 2)
            dp[i] = abs(height[i] - height[i-1]) + dp[i-1];
        else dp[i] = min(abs(height[i] - height[i-1]) + dp[i-1], abs(height[i] - height[i-2]) + dp[i-2]);
    }
    return dp[n];
}

int main()
{
   int n,k;
   cin >> n;
   vector<int> height(n+1);
   for(int i=1;i<=n;i++)
   {
       cin>>height[i];
   }
   cout << solve(height, n);
   return 0;
}


Measured memory_bytes: 1024
n, m = map(int, input().split())
h = list(map(int, input().split()))
a = [0]*n
ans = n
for i in range(m):
  b, c = map(int, input().split())
  b -= 1
  c -= 1
  a[b] += 1
  a[c] += 1
  if h[b] == h[c]:
    if a[b] == 1 and a[c] == 1:
      ans -= 2
    elif a[b] == 1 and a[c] != 1:
      ans -= 1
    elif a[b] != 1 and a[c] == 1:
      ans -= 1
  if h[b] > h[c]:
    a[b] -= 1
    if a[c] == 1:
      ans -= 1
  if h[b] < h[c]:
    a[c] -= 1
    if a[b] == 1:
      ans -= 1
print(ans)

Measured memory_bytes: 19996
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main {
  	static int count;
	
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] A = new int[n];
		String[] str = br.readLine().split(" "); 
		
		for(int i = 0; i < n; i++){
			A[i] = Integer.parseInt(str[i]);
		}
		
		mergeSort(A, 0, A.length);
		
		for(int i = 0;  i < n; i++){
			if(i != n - 1){
				System.out.print(A[i] + " ");
			}else{
				System.out.println(A[i]);
			}
		}
		System.out.println(count);
	}
	
	public static void mergeSort(int[] array, int low, int high){
		if(low + 1 < high){
			int middle = (low + high) / 2;
			mergeSort(array, low, middle);
			mergeSort(array, middle, high);
			merge(array, low, middle, high);
		}
	}
	
	public static void merge(int[] array, int low, int middle, int high){
		int n1 = middle - low;
		int n2 = high - middle;
		
		int[] L = new int[n1 + 1];
		int[] R = new int[n2 + 1];
		
		for(int i = 0; i < n1; i++){
			L[i] = array[low + i];
		}
		for(int i = 0; i < n2; i++){
			R[i] = array[middle + i];
		}
		
		L[n1] = (int) Double.POSITIVE_INFINITY; 
		R[n2] = (int) Double.POSITIVE_INFINITY;
		
		int i = 0;
		int j = 0;
		
		for(int k = low; k < high; k++){
			if(L[i] <= R[j]){
				array[k] = L[i];
				i++;
			}else{
				array[k] = R[j];
				j++;
			}
			count++;
		}
	}
}

Measured memory_bytes: 173240
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define pb push_back
#define mp make_pair
#define F .first
#define S .second 
using ll=long long;
using ld=long double;
const ll INF = 1LL<<60;
const ll mod=1e9+7;
using namespace std;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }


int main(){
    ll h1,m1,h2,m2,k;
    cin>>h1>>m1>>h2>>m2>>k;
    ll ans=0;
    if(h1==h2)ans=m2-m1;
    else{
        ans=60-m1+m2+60*(h2-h1-1);
    }
    cout<<ans-k;
}

Measured memory_bytes: 3632
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
using namespace std;
using ll=long long;
using ld=long double;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
struct edge{ll to,cost;};
struct edge2{ll from,to,cost;};

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll H,W,M;
    cin >> H >> W >> M;
    vl h(M),w(M);
    vl cnt0(H),cnt1(W);
    ll mxh=0,mxw=0;
    rep(i,M){
        cin >> h[i] >> w[i];
        h[i]--;w[i]--;
        cnt0[h[i]]++;cnt1[w[i]]++;
        chmax(mxh,cnt0[h[i]]),chmax(mxw,cnt1[w[i]]);
    }
    ll nowh=0,noww=0;
    rep(i,H){
        if(cnt0[i]==mxh){
            nowh++;
        }
    }
    rep(i,W){
        if(cnt1[i]==mxw){
            noww++;
        }
    }
    ll now=0;
    rep(i,M){
        if(cnt0[h[i]]==mxh&&cnt1[w[i]]==mxw){
            now++;
        }
    }
    //cout << now << ' ' << nowh << ' ' << noww << '\n';
    cout << (now==nowh*noww?mxh+mxw-1:mxh+mxw) << endl;
}
/*
overflow checked?
corner case checked?
boundary checked?
not TLE in worst case checked?
*/

Measured memory_bytes: 12684
#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<int, int>;

const ll mod = 1000000007;
const double eps = 1e-8;

#ifdef DEBUG
#include "inc/debug.hpp"
#else
#define debug(...) 42
#endif

int main() {
    int H1, M1, H2, M2, K;
    cin >> H1 >> M1 >> H2 >> M2 >> K;

    int m1 = (H1 * 60 + M1);
    int m2 = (H2 * 60 + M2);
    cout << max(0, m2 - K - m1) << endl;

    return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define arep(a,i,n) for(int i=(a);i<(n);i++)
#define rep(i,n) for(int i=0;i<(n);i++)
#define cinf(x,n) for(int i=0;i<(n);i++)cin>>x[i];
#define coutf(x,n) for(int i=0;i<(n);i++)cout<<x[i]<<endl;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

int main(){
	ll n,a,b;
	cin >> n >> a >> b;
	ll q = n/(a+b);
	ll r = n%(a+b);
	if(r < a)
		cout << q*a+r << endl;
	else
		cout << (q+1)*a << endl;
}

Measured memory_bytes: 256
#AGC039-A Connection and Disconnection
"""
sをk回繰り返して得られる文字列tを、全て隣り合う文字が異なるようにする
為に必要な操作回数を求めよ
解法：
最初と最後だけ愚直にカウント
あとは中間部分を連結してそれをk-1回繰り返す
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
s = readline().rstrip().decode('utf-8')
k = int(readline())
first = 0
last = 0
l = 0
r = len(s)

#全部同じ文字だとまずい
if len(set(s)) == 1:
    print(len(s)*k//2)
    exit()

if s[0] == s[-1]:
    res = s[0]
    for idx,i in enumerate(s):
        if i == res:
            first += 1
        else:
            l = idx
            break
    res = s[-1]
    for idx,i in enumerate(s[::-1]):
        if i == res:
            last += 1
        else:
            r = len(s)-idx
            break

count = 0
res = ""
for i in s[l:r]:
    if res == "":
        res = i
    elif res == i:
        count += 1
        res = ""
    else:
        res = i

print(first//2+last//2+(first+last)//2*(k-1)+count*k)

Measured memory_bytes: 38496
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;
const int mod = 1e9+7;

int main() {
    int a, b, c; cin >> a >> b >> c;
    int x = max({a,b,c});
    int y = (a+b+c)-x;
    if (x == y) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
def solve(n, y):
    tmp1000 = n * 1000
    if tmp1000 > y:
        return -1, -1, -1
    diff = y - tmp1000
    for y in range(diff // 4000 + 1):
        tmp5000 = y * 4000
        if diff - tmp5000 < 0:
            break
        if (diff - tmp5000) % 9000 == 0:
            x = (diff - tmp5000) // 9000
            if x >= 0 and x + y <= n:
                return x, y, n - x - y
    return -1, -1, -1


print(*solve(*map(int, input().split())))


Measured memory_bytes: 3060
n = gets.to_i
ss = gets.chomp.chars
ans = ss.count("R") * ss.count("G") * ss.count("B")

0.upto(n) do |i|
  a = ss[i]

  1.upto(n / 2) do |d|
    j = i + d
    b = ss[j]
    next if a == b

    k = i + d * 2
    next unless k < n

    c = ss[k]
    ans -= 1 if a != b && b != c && c != a
  end
end

puts ans


Measured memory_bytes: 14340
u, s, e, w, n, d = input().split()
insts = input()
for inst in insts:
    if inst == 'N':
        u, s, n, d = s, d, u, n
    elif inst == 'E':
        u, e, w, d = w, u, d, e
    elif inst == 'S':
        u, s, n, d = n, u, d, s
    elif inst == 'W':
        u, e, w, d = e, d, u, w
print(u)

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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    if (N % 2 == 1) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = 0;
    ll p = 10;
    while (p <= N) {
        ans += N / p;
        p *= 5LL;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
n,c=map(int,input().split())
stc=[list(map(int,input().split())) for _ in range(n)]
cs_dc={}
dc={}
for s,t,c in stc:
  if c in dc:
    dc[c][s]+=1
    dc[c][t]-=1
  else:
    dc[c]=[0]*(10**5+2)
    dc[c][s]+=1
    dc[c][t]-=1
    cs_dc[c]=[0]*(10**5+2)

for i in range(10**5+1):
  for ci in dc:
    cs_dc[ci][i+1]=cs_dc[ci][i]+dc[ci][i+1]
ans=0
for i in range(10**5+1):
  tmp=0
  for ci in dc:
    tmp+=max(cs_dc[ci][i:i+2])
  ans=max(ans,tmp)
print(ans)

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

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

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;

typedef set<int> si;
typedef set<ii> sii;
typedef set<ld> sd;
typedef set<ll> sl;

typedef map<int, int> mii;
typedef priority_queue<int> pqi;
typedef queue<int> qi;
 
#define mp make_pair
#define pb push_back
#define f first
#define s second

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  
  	int n, k;
  	cin >> n >> k;
  	vi a(n); for (auto &x : a) cin >> x;
  	vi dp(n, numeric_limits<int>::max()); dp[0] = 0;
  	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= k and i + j < n; j++) dp[i + j] = min(dp[i + j], dp[i] + abs(a[i] - a[i + j]));
    }
    cout << dp[n - 1] << endl;
}

/*
USE LONG LONG!!!!

          .=     ,        =.
  _  _   /'/    )\,/,/(_   \ \
   `//-.|  (  ,\\)\//\)\/_  ) |
   //___\   `\\\/\\/\/\\///'  /
,-"~`-._ `"--'_   `"""`  _ \`'"~-,_
\       `-.  '_`.      .'_` \ ,-"~`/
 `.__.-'`/   (-\        /-) |-.__,'
   ||   |     \O)  /^\ (O/  | .        <-  BESSIE THE COW
   `\\  |         /   `\    /
     \\  \       /      `\ /
      `\\ `-.  /' .---.--.\
        `\\/`~(, '()      ('
         /(O) \\   _,.-.,_)    
        //  \\ `\'`      /
       / |  ||   `""""~"`
     /'  |__||
           `o
*/

Measured memory_bytes: 1024
#pragma region Template
#include <bits/stdc++.h>
using namespace std;
struct ios_accelerate { ios_accelerate() { ios::sync_with_stdio(false); cin.tie(nullptr); } } CALL;

#define REP(i, n) for(int i = 0; i < n; i++)
#define RNG(i, a, b) for(int i = a; i < b; i++)
#define RBF(i, v) for(auto& i : v)
#define ALL(x) x.begin(), x.end()

using LL = long long;
using UL = unsigned long;
using ULL = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
template<typename T> using P = pair<T, T>;

const double PI = 3.141592653589793;
const int MOD = 1000000007;
const LL INF64 = static_cast<LL>(1e18) + 2;
const int INF = static_cast<int>(1e9) + 2;

template<typename T> inline void upsort(vector<T>& x) { sort(x.begin(), x.end()); }
template<typename T> inline void downsort(vector<T>& x) { sort(x.begin(), x.end(), greater<T>()); }
template<typename T> inline void col(T x) { cout << x << '\n'; }
template<> inline void col(double x) { cout << fixed << setprecision(12) << x << '\n'; }
#pragma endregion

template<typename T> T combination(T N, T K) {
	if (N < K) return 0;
	if (N == K || K == 0) return 1;
	vector<T> v(N, 1);
	T prev1 = 1, prev2 = 1; // prev1 = n−1Ck−1, prev2 = n−1Ck

	for (T n = 2; n <= N; n++) {
		prev1 = 1;
		T k = 1;
		while (k < n && k <= K) {
			prev2 = v[k];
			v[k++] = prev1 + prev2;
			//v[k++] = (prev1 + prev2) % MOD; // 余りを答えるように要求された時用
			prev1 = prev2;
		}
	}
	return v[K];
}

signed main()
{
	int n, m;
	cin >> n >> m;

	int ans = combination(n, 2) + combination(m, 2);
	col(ans);
	return 0;
}


Measured memory_bytes: 3664
#include <iostream>
#include <math.h>
using namespace std;
int main() {
int n,a[101];
cin>>n;
for(int i=0;i<n;i++){
  cin>>a[i];
}
for(int w=n-1;w>-1;w--){
  if(w!=0){
   cout<<a[w]<<" ";
  }
  else{
   cout<<a[w]<<'\n';
  }
}
}


Measured memory_bytes: 1160
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		new Main().solve();
	}
	
	int N;
	int[]a; //max4800
	void solve(){
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		a=new int[N];
		int[] color=new int[9];
		
		for(int i=0;i<N;i++){
			a[i]=sc.nextInt();
			if(a[i]<3200)color[a[i]/400]++;
			else color[8]++;
		}
		
		int cnt=0;
		for(int i=0;i<8;i++){
			if(color[i]>0){
				cnt++;
			}
		}
		
		if(color[8]>0){
			if(cnt==8)System.out.println(8+" "+(cnt+color[8]));
			else if(cnt==0)System.out.println(1+" "+color[8]);
			else System.out.println(cnt+" "+(cnt+color[8]));
		}else{
			System.out.println(cnt+" "+cnt);
		}
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s, t;
  cin >> s >> t;
  int ans = s.size();
  for(int i=0; i<=s.size() - t.size(); i++){
    int cnt = 0;
    for(int j=0; j<t.size(); j++){
      if(s[i + j] != t[j]) cnt++;
    }
    ans = min(cnt, ans);
  }
  cout << ans << endl;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1001001001;
const ll LINF = 1001001001001001001;
#define fori(i,a,b) for(ll i=(a);i<=(b);i++)
#define repi(i,n) fori(i,0,(n)-1)
#define forr(i,a,b) for(ll i=(b);i>=(a);i--)
#define repr(i,n) forr(i,0,(n)-1)
#define all(x) (x).begin(),(x).end()
#define fill(a,x) memset(a,x,sizeof(a))
#define vec vector<ll>
#define pb push_back
#define mp make_pair
#define pcnt __builtin_popcount
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(b<a){a=b;return 1;}return 0;}

#define N 3000
double p[N];
double dp[N+1][N+1];
void solve(){
    ll n;cin>>n;
    repi(i,n)cin>>p[i];
    dp[0][0]=1;
    fori(i,1,n){
        fori(j,0,i){
            dp[i][j]=dp[i-1][j]*(1-p[i-1]);
            if(j>0)dp[i][j]+=dp[i-1][j-1]*p[i-1];
        }
    }
    double ans=0;
    fori(i,n/2+1,n)ans+=dp[n][i];
    cout.precision(10);
    cout<<ans<<endl;
}

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


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

using namespace std;

string pat;

char change(char ch, int x)
{
    int p = pat.find(ch);
    return pat[(p - x + 52) % 52];
}

void make_pat()
{
    for (int i = 0; i < 26; i++) {
        pat += (char)('A' + i);
    }
    for (int i = 0; i < 26; i++) {
        pat += (char)('a' + i);
    }
}

int main()
{
    make_pat();
    
    int N;
    while (cin >> N, N) {
        vector<int> a(N);
        for (int i = 0; i < N; i++) {
            cin >> a[i];
        }
        string s;
        cin >> s;
        for (int i = 0; i < (int)s.size(); i++) {
            int x = a[i % N];
            cout << change(s[i], x);
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 3160
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//String t= sc.next();
		String buff= "";
		//double n = sc.nextInt()/1000.0;
		int m = sc.nextInt();
		//int k = sc.nextInt();
		String s=sc.next();
		long count=0,flag=0;
		long count1=0,count2=0;
		int count3=0;
		int[] array = new int[3];
		/*array[0]=n-m;
		array[1]=n*m;
		array[2]=n+m;*/
		Arrays.sort(array);

		for(int i=0;i<s.length();i++) {
			if((char)(s.charAt(i)+m)>'Z') {
				buff+=String.valueOf((char)(s.charAt(i) + m-26));
			}else {
				buff+=String.valueOf((char)(s.charAt(i) + m));
			}
			//System.out.println((char)s.charAt(i));
		}

		/*if(s.length()%2==0) {
			for(int i=0;i<s.length()/2;i++) {
				for(int j=s.length();j>s.length()/2;j--) {
					if(!s.substring(i,i+1).equals(s.substring(j-1,j)))count++;
				}
			}
			System.out.println(count);
		}else{
			for(int i=0;i<s.length()/2;i++) {
				for(int j=s.length();j>s.length()/2;j--) {
					if(!s.substring(i,i+1).equals(s.substring(j-1,j)))count++;
				}
			}
			System.out.println(count);
		}*/

		System.out.println(buff);
	}
}




Measured memory_bytes: 148152
#include <stdio.h>
#include <limits.h>
#include <algorithm>
 
using namespace std;
 
long long int sum = 0;
 
 
void merge(int A[],int left,int mid, int right){
    int a1 = mid - left;
    int a2 = right - mid;
    int l[a1+1],r[a2+1];
    for(int i = 0; i < a1; i++) l[i] = A[left + i];
    for(int i = 0; i < a2; i++) r[i] = A[mid + i];
    l[a1] = r[a2] =  INT_MAX;
 
    int i = 0, j = 0;
    for(int k = left;k < right; k++){
        if(l[i] < r[j]){
            A[k] = l[i++];
        }else{
            A[k] = r[j++];
            sum += a1 - i;
        }
    }
}
 
void mergeSort(int A[],int left,int right){
    if(left+1 < right){
        int mid = (left+right)/2;
        mergeSort(A,left,mid);
        mergeSort(A,mid,right);
        merge(A,left,mid,right);
    }
}
 
int main(){
    int n;
    scanf("%d",&n);
    int A[n];
    for(int i = 0; i < n; i++) scanf("%d",&A[i]);
 
    mergeSort(A,0,n);
 
    printf("%lld\n",sum);
 
}


Measured memory_bytes: 4220