akhauriyash/Code-Regression huggingface dataset:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18

N,C=rl()
stc = [rl() for _ in range(N)]
stc.sort(key=lambda x:(x[2],x[0]))
nstc = []
for s,t,c in stc:
    if len(nstc) != 0 and nstc[-1][2] == c and nstc[-1][1] == s:
        nstc[-1][1] = t
    else:
        nstc.append([s,t,c])

n = len(nstc)

TT=[0]*(2*10**5+5)
for i in range(n):
    TT[2*nstc[i][0] - 1] += 1
    TT[2*nstc[i][1]] -= 1
for i in range(1,len(TT)):
    TT[i] += TT[i-1]
print(max(TT))

Measured memory_bytes: 36892
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const ll INF = 1e18L+5;
int main(){
	ll n,w;
	cin>>n>>w;
	ll sum = 0;
	vector<ll> weight(n),value(n);
	for(ll i=0;i<n;i++){
		cin>>weight[i]>>value[i];
		sum += value[i];
	}
	
	vector<ll> dp(sum+1,INF);
	dp[0] = 0;
	for(ll i=1;i<=n;i++){
		for(ll j = sum-value[i-1];j>=0;j--){
				dp[j+value[i-1]] = min(dp[j+value[i-1]],dp[j]+weight[i-1]);
		}
	}
	ll ans = 0;
	for(ll i=0;i<=sum;i++){
		if(dp[i]<=w) ans = max(ans,i);
	}
	cout<<ans<<"\n";
}

Measured memory_bytes: 1024
/*
ID: Aman Raj
LANG: C++
TASK: subset
*/
#include<iostream>
#include <stdio.h>
//#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#include<math.h>
typedef  long long int ll;
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
//hr
using namespace std;
using namespace __gnu_pbds;
//hy
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
//#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
//#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <fstream>
// find_by_order()  // order_of_key
typedef tree<
	int,
	null_type,
	less<int>,
	rb_tree_tag,
	tree_order_statistics_node_update>
	ordered_set;
  //# define mod 1e9+7
   ll gcd(ll a,ll b)
   {
       if(a==0)return b;
       return gcd(b%a,a);
   }
//kj
int main()
{
   ll n;cin>>n;
     vector<ll> v(n);
      for(ll i=0;i<n;i++)cin>>v[i];
      vector<ll> vballs(n+1,0);
      ll m=0;
      for(ll i=n;i>=1;i--)
      {
          ll a=v[i-1];
          ll j=i+i;
           ll balls=0;
           while(j<=n)
           { if(vballs[j]==1)balls++;
              j+=i;
           }
          if(a==1&&balls%2==0)
          {
              vballs[i]=1;m++;
          }
         else if(a==0&&balls%2==1){vballs[i]=1;m++;}

      }
      cout<<m<<endl;

           for(ll i=1;i<=n;i++)if(vballs[i]>0)cout<<i<<" ";
      return 0;
}


Measured memory_bytes: 3968
#include<stdio.h>
char a[100],b[100],c[100];
int main()
{
    int i,j,s1,s2;
    scanf("%s[^\t]",a);
    scanf("%s[^\t]",b);
    scanf("%s[^\t]",c);
    for(s1=0;a[s1]!='\0';s1++);
    for(s2=0;b[s2]!='\0';s2++);
    if(a[s1-1]==b[0] && b[s2-1]==c[0])
    {
        printf("YES\n");
    }
    else
    {
        printf("NO\n");
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+5;

int main(){
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
	
	int n, k;
	cin >> n >> k;
	unordered_map<int, int> m;
	for(int i=0,x;i<n;++i){
		cin >> x;
		++m[x];
	}
	vector<int> v;
	for(auto &kv:m){
		v.push_back(kv.second);
	}
	sort(v.begin(), v.end());
	int ans = 0;
	for(int i=(int)v.size()-k-1;i>=0;--i) ans += v[i];
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 10312
func = list(input())
mont = []
num=1
if len(func)==1 and func[0]==">":
  print(1)
else:
  for i in range(len(func)):
    if i == len(func)-1:
      if func[i]=="<":
        mont.append(num)
        mont.append(0)
      else:
        
        mont.append(num)
    elif i==0 and func[0] ==">":
      mont.append(0)
      num=1
    elif func[i] == "<" and func[i+1]==">":
      mont.append(num)
      num=0
    elif func[i] == ">" and func[i+1]=="<":
      mont.append(num)
      num=0
    else:
      pass
    num += 1

  count=0
  for i in range(0,len(mont),2):
    if mont[i] >= mont[i+1]:
      count+= mont[i]*(mont[i]+1)//2 + mont[i+1]*(mont[i+1]-1)//2
    else:
      count+= mont[i]*(mont[i]-1)//2 + mont[i+1]*(mont[i+1]+1)//2
  print(count)

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

int main() {
    int N, C;
    cin >> N >> C;
    vector<vector<int>> D(C, vector<int>(C));
    rep(i, C) {
        rep(j, C) {
            cin >> D[i][j];
        }
    }

    vector<vector<int>> E(N, vector<int>(N));
    rep(i, N) {
        rep(j, N) {
            cin >> E[i][j];
            E[i][j]--;
        }
    }

    vector<vector<int>> G(3, vector<int>(C));
    rep(i, N) {
        rep(j, N) {
            G[(i + j) % 3][E[i][j]]++;
        }
    }

    int ans = __INT32_MAX__;
    // i+j%3 == 0
    for (int c1 = 0; c1 < C; c1++) {
        // i+j%3 == 1
        for (int c2 = 0; c2 < C; c2++) {
            if (c1 == c2) continue;
            // i+j%3 == 2
            for (int c3 = 0; c3 < C; c3++) {
                if (c1 == c3 || c2 == c3) continue;

                int x = 0;
                // aをc1に塗り替える
                for (int a = 0; a < C; a++) {
                    x += D[a][c1] * G[0][a];
                }

                // aをc2に塗り替える
                for (int a = 0; a < C; a++) {
                    x += D[a][c2] * G[1][a];
                }

                // aをc3に塗り替える
                for (int a = 0; a < C; a++) {
                    x += D[a][c3] * G[2][a];
                }

                ans = min(ans, x);
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 4504
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x) x
#define rep(...) MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T1, class T2>bool chmax(T1& a, const T2& b) { return a < b ? a = b, 1 : 0; }
template<class T1, class T2>bool chmin(T1& a, const T2& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int main() {
    int A, B;
    cin >> A >> B;

    write(max({ A + B, A - B, A * B }));
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int n,i,j,tmp,r=1,t;
	int arr[100];
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&arr[i]);
	}
	for(i=0;i<n;i++)
	{
		for(j=i+1;j<n;j++)
		{
			if(arr[i]<arr[j])
			{
				tmp=arr[i];
				arr[i]=arr[j];
				arr[j]=tmp;
			}
		}
	}
	t=arr[0];
	for(i=1;i<n;i++)
	{
		if(t!=arr[i])
		{
			t=arr[i];
			r++;
		}
	}
	printf("%d\n",r);
	return 0;
}

Measured memory_bytes: 128
fun main(args: Array<String>) {
    val n = readLine()!!
    var numN = n.toLong()

    var ans = ""

    while(numN != 0L) {
        if(numN % 2 != 0L) {
            numN--;
            ans = "1$ans";
        } else {
            ans = "0$ans";
        }
        numN /= -2;
    }

    if(ans == "") {
        println("0");
    }else {
        println(ans);
    }

}



Measured memory_bytes: 31840
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int N;
 
  bool flag = true;
  cin >> N;
   int x[N];
  for(int i=0; i < N;i++){
  cin >> x[i];
  }
  for(int i =0; i < N; i++){
    if(x[i] % 2 == 0){
    if(x[i] % 3 != 0 && x[i] % 5 != 0)
      flag = false;
    }
    
       }
  if(flag == true)
    cout << "APPROVED" << endl;
  else
    cout << "DENIED" << endl;
 
 
}

Measured memory_bytes: 256
// Author -- Frame

#include<bits/stdc++.h>

#define lowbit(x) ((x)&(-x))
#define Finline __inline__ __attribute__ ((always_inline))
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
#define SZ(x) ((int)x.size())
#define mkpr std::make_pair
#define pb push_back

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef std::pair<int,int> pi;
typedef std::pair<int,int> pl;

const int inf=0x3f3f3f3f,Inf=0x7fffffff;
const ll INF=0x7fffffffffffffff;

Finline uint rnd()
{
	static uint seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
template <typename _Tp>_Tp gcd(const _Tp &a,const _Tp &b){return (!b)?a:gcd(b,a%b);}
template <typename _Tp>Finline _Tp abs(const _Tp &a){return a>=0?a:-a;}
template <typename _Tp>Finline _Tp max(const _Tp &a,const _Tp &b){return a<b?b:a;}
template <typename _Tp>Finline _Tp min(const _Tp &a,const _Tp &b){return a<b?a:b;}
template <typename _Tp>Finline void chmax(_Tp &a,const _Tp &b){(a<b)&&(a=b);}
template <typename _Tp>Finline void chmin(_Tp &a,const _Tp &b){(b<a)&&(a=b);}
template <typename _Tp>Finline void read(_Tp &x)
{
	char ch(getchar());
	bool f(false);
	while(ch<48||ch>57) f|=ch==45,ch=getchar();
	x=ch&15,ch=getchar();
	while(ch>=48&&ch<=57) x=(((x<<2)+x)<<1)+(ch&15),ch=getchar();
	if(f) x=-x;
}
template <typename _Tp,typename... Args>Finline void read(_Tp &t,Args &...args)
{
	read(t);read(args...);
}
Finline int read_str(char *s)
{
	char ch(getchar());
	while(ch==' '||ch=='\r'||ch=='\n') ch=getchar();
	char *tar=s;
	*tar=ch,ch=getchar();
	while(ch!=' '&&ch!='\r'&&ch!='\n'&&ch!=EOF) *(++tar)=ch,ch=getchar();
	return tar-s+1;
}

const int N=5005;
int mod;
template<typename _Tp1,typename _Tp2>Finline void add(_Tp1 &a,_Tp2 b){(a+=b)>=mod&&(a-=mod);}
int dp[N];
int main()
{
	int n;
	read(n,mod);
	dp[0]=1;
	for(int i=2;i<=n;++i)
	{
		int v=min(n-i+1,i-2)+1;
		for(int k=v;k<=n;++k)
		{
			add(dp[k],dp[k-v]);
		}
	}
	int ans=0;
	for(int i=0;i<=n;++i) add(ans,1ll*dp[i]*(n-i)%mod);
	printf("%d\n",ans);
	return 0;
}


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

import java.math.BigDecimal;
import java.math.MathContext;

public class Main{
  public static void main(String[] args){
	  Scanner sc = new Scanner(System.in);
	  int a = sc.nextInt();
	  int b = sc.nextInt();
	  int c = sc.nextInt();
	  
	  BigDecimal ab = new BigDecimal(a);
	  BigDecimal bb = new BigDecimal(b);
	  BigDecimal cb = new BigDecimal(c);
	  
	  BigDecimal ar = sqrt(ab,50);
	  BigDecimal br = sqrt(bb, 50);
	  BigDecimal cr = sqrt(cb, 50);
	 
	  BigDecimal x = ar.add(br);
	  BigDecimal ans = cr.subtract(x);
	  
	 if( x.compareTo(cr) < 0)
		  out.println("Yes");
	  else
		  out.println("No");
		  
  	}  	
  public static BigDecimal sqrt(BigDecimal a, int scale){
      //とりあえずdoubleのsqrtを求める
      BigDecimal x = new BigDecimal(
              Math.sqrt(a.doubleValue()), MathContext.DECIMAL64);
      if(scale < 17) return x;

      BigDecimal b2 = new BigDecimal(2);
      for(int tempScale = 16; tempScale < scale; tempScale *= 2){
          //x = x - (x * x - a) / (2 * x);
          x = x.subtract(
                  x.multiply(x).subtract(a).divide(
                  x.multiply(b2), scale, BigDecimal.ROUND_HALF_EVEN));
      }
      return x;
  }
  }	

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

int main(){
    int N, X;
    cin >> N >> X;
    vector<int> L(N);
    int count = 0;
    int D = 0;

    for (int i = 0; i < N; i++){
        cin >> L.at(i);
    }

    while (D <= X && count < N){
        D = D + L.at(count);
        count++;
    }
    if (D > X ){
        cout << count << endl;
    }
    else {
        cout << count + 1 << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include <iomanip>
#include <ios>
#include <vector>
#include <string>
#include <algorithm>
#include <string>
#include<limits>
#include<cstdlib>
#include<functional>
#include<cassert>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
//#include <bits/stdc++.h>//atcoderでsqrtを使うときに必要
#define fi(p) for(int i=0;i<(p);i++)
#define ce(d) cout<<d<<endl;
#define ll long long
#define sorts(c) sort((c).begin(),(c).end());

using namespace std;

void solve() {
	int n, k;
	cin >> n >> k;

	vector<int> p(n);

	fi(n) {
		cin >> p[i];
	}

	sort(p.begin(),p.end());

	int res = 0;

	fi(k) {
		res += p[i];
	}

	ce(res);

	
}

int main()
{
	solve();

	int a;//止める用
	cin >> a;
	return 0;
}

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

int main() {
  int N;
  cin>>N;
  int z=0;
  for(int i=0;i<N;i++){
    string x;
    cin>>x;
    if(x=="Y"){z++;}
  }
if(z==0){cout<<"Three"<<endl;}
else{cout<<"Four"<<endl;}
}


Measured memory_bytes: 256
import math
Alist = []
Blsit = []
yakusuu = []
A,B,K = map(int,input().split())
Alist = [i for i in range(1,A+1) if A%i==0]
Blist= [i for i in range(1,B+1) if B%i==0]
for a in Alist:
    for b in Blist:
        if a==b:
            yakusuu.append(a)
yakusuu.sort()
print(yakusuu[-K])

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int main()
{
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  if ((A+B)>(C+D)) {
    cout << "Left" << endl;
  } else if ((A+B)<(C+D)) {
    cout << "Right" << endl;
  } else {
    cout << "Balanced" << endl;
  }
  return 0;
}


Measured memory_bytes: 3628
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define N 100010
#define mod 1000000007
#define ll long long
using namespace std;
int num[N],tot;
ll n,k,f[N];
ll ksm(ll a,ll b=mod-2)
{
	if(b==0) return 1;
	if(b==1) return a;
	ll q=ksm(a,b>>1);
	if(b&1) return q*q%mod*a%mod;
	return q*q%mod;
}
int main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i*i<=n;i++)
	if(n%i==0)
	{
		num[++tot]=i;
		if(i*i!=n) num[++tot]=n/i;
	}
	sort(num+1,num+tot+1);
	ll ans=0;
	for(int i=1;i<=tot;i++)
	{
		f[i]=ksm(k,(num[i]+1)>>1);
		for(int j=1;j<i;j++)
		if(num[i]%num[j]==0) f[i]=(f[i]-f[j]+mod)%mod;
	}
	for(int i=1;i<=tot;i++)
	ans=(ans+f[i]*num[i]/(num[i]&1?1:2))%mod;
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i , n) for (int i = 0; i < (int)(n); i++)
const int INF = 1<<29;
using namespace std;
using ll = long long;
int main(){
	int h , w , m;
	cin >> h >> w >> m;
	vector <int> c[h];
	int t[w] = {0};
	int a , b;
	for(int i = 0; i < m; i++){
        cin >> a >> b;
		a--;
        b--;
		c[a].push_back(b);
		t[b]++;
	}
	multiset <int> d;
	for(int i = 0; i < w; i++){
		d.insert(t[i]);
	}
	int ans = 0;
	for(int i = 0; i < h; i++){
		vector <int> e;
		int n = c[i].size();
		for(auto j : c[i]){
			d.erase(d.find(t[j]));
			ans = max(ans , t[j] + n - 1);
			e.push_back(j);
		}
		if(d.size()){
			ans = max(ans , n + *(d.rbegin()));
        }
		for(auto j : e){
			d.insert(t[j]);
        } 
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 35220
from heapq import heappush, heappop
import queue
import re
import math
import functools

def s_raw():
    return input().rstrip("\r")

def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return list(map(int, ss_raw()))


INF = 1 << 29


def make1d_arr(n, val=INF):
    return [val for i in range(n)]


def make2d_arr(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]


def gcd(a, b):
    if(b == 0):
        return a
    return gcd(b, a % b)


def BFord(n,es):
    v_cost = [INF]*n
    v_cost[0] = 0
    for v in range(n*2):
        for e in es:
            frm = e[0]
            to = e[1]
            if v_cost[to] > v_cost[frm]+e[2]:
                v_cost[to] = v_cost[frm]+e[2]
                if v >= n:
                    v_cost[to] = -INF
        if v == n-1:
            prev = v_cost[:]
    v_cost = [-INF if prev[idx]!=v_cost[idx] else v_cost[idx] for idx in range(n)]
    return v_cost
    

def main():
    TS = ["Sunny", "Cloudy", "Rainy"]
    S = s_raw()
    for i in range(len(TS)):
        if S ==TS[i]:
            return TS[(i+1)%3]
if __name__ == "__main__":
    print(main())


Measured memory_bytes: 38636
#include "bits/stdc++.h"
using namespace std;
int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    string s;
    cin>>n;
    cin>>s;
    int len=s.length();
    for(int i=0;i<s.length();i++){
        int tmp=s[i]-'A';
        if(tmp+n<26){
            printf("%c",(char)(65+tmp+n));
        }else{
            int b=25-tmp;
            printf("%c",(char)(65+(n-b-1)));
        }
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 256
# include <cmath>
# include <iostream>
# include <queue>
# include <set>
# include <stack>
# include <string>
# include <vector>


using namespace std;


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

    int ans = 0;
    char prev = '-';
    for (int i=0; i<n; i++) {
        if (prev != s[i]) {
            ans++;
        }
        prev = s[i];
    }

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


Measured memory_bytes: 1144
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;

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

    uint h = s / 3600;
    s %= 3600;
    uint m = s / 60;
    s %= 60;

    printf("%u:%u:%u\n", h, m, s);
}



Measured memory_bytes: 3156
# セグメントツリー
#############################################################

def segfunc(x, y):
    return max(x, y)

ide_ele = 0

class SegTree:

    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res
#############################################################


N, K = map(int, input().split())

# val[i] = 最後の値がiである、最長の部分列の長さ
val = [0] * 300010
seg = SegTree(val, segfunc, ide_ele)
ans = 0

for i in range(N):
    a = int(input())
    # (a-K, a-K+1, ..., a+K-1, a+K の max) + 1 に更新する
    # 両端が範囲内に収まるように調整
    l = max(a - K, 0)
    r = min(a + K, 300000)
    # 半開区間
    tmp = seg.query(l, r + 1) + 1
    ans = max(ans, tmp)
    seg.update(a, tmp)

print(ans)


Measured memory_bytes: 113724
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define P pair<ll,ll>
#define rep(i,n) for(ll (i)=0; (i)<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll d;cin>>d;
  if(d==22) puts("Christmas Eve Eve Eve");
  if(d==23) puts("Christmas Eve Eve");
  if(d==24) puts("Christmas Eve");
  if(d==25) puts("Christmas");
  return 0;
}

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

int main(){
    int a,b;
    cin >> a >> b;
    int c=b-a;
    int total=0;
    for(int i=1;i<=c;i++){
        total += i;
    }
    int ans = total-b;
    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>

using namespace std;
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()

// int DP[MEM_SIZE][MEM_SIZE] = {0};
// int GMEM[MEM_SIZE][MEM_SIZE] = {0};
template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

void solve(void)
{
  int N,M; cin>>N; cin>>M;
  int SUM = 0;
  for (int i = 0; i < M; i++)
  {
    int X;cin>>X;
    SUM += X;   
  }
  int P = N - SUM;
  if(P < 0)
  {
    cout<<-1<<endl;
  }
  else
  {
    cout<<P<<endl;
  }
  
  return;
}

int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();

  return 0;
}


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

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

typedef long long ll;

const int N=1e5+5;

template<typename T> void read(T &x){
   x=0;int f=1;
   char c=getchar();
   for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
   for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

char s[10];

int main()
{
    scanf("%s",s);
    if(s[1]=='R')puts("ABC");
    else puts("ARC");
    return 0;
}

Measured memory_bytes: 3764
a, b, c = list(map(int, input().split(' ')))

checker = {}
d = a
while(True):
    m = (d - c) % b
    checker.setdefault(m, False)
    
    if m == 0:
        print('YES')
        break
    elif checker[m]:
        print('NO')
        break
    else:
        checker[m] = True
        d += a



Measured memory_bytes: 3060
#include <iostream>
#include<math.h>
using namespace std;

int main()
{
    
    long long n,d;
    cin>>n>>d;
    int res=0;
    for(int i=0;i<n;i++){
     long long x,y;
     cin>>x>>y;
     if(sqrt(x*x+y*y)<=d) res++;
    }
   cout<<res;
   return 0;
}

Measured memory_bytes: 3676
// #include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
// #include <algorithm>
#define pb push_back
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// #define cerr if(0)cerr
using namespace std;
typedef long long LL;

const int N=100010;
const LL  I=1e18;
int n;
LL T[N][3],DP[N][3];

LL maxi(LL x, LL y)
{
  if(y>x)return y;
  return x;
}

int main()
{
  // boost;
  scanf("%d",&n);
  for(int i=1; i<=n; i++)
  {
    for(int j=0; j<3; j++)
    {
      scanf("%lld",&T[i][j]);
      if(i==1)DP[i][j]=T[i][j];
    }
  }
  for(int i=2; i<=n; i++)
  {
    DP[i][0]=maxi(DP[i-1][1],DP[i-1][2])+T[i][0];
    DP[i][1]=maxi(DP[i-1][0],DP[i-1][2])+T[i][1];
    DP[i][2]=maxi(DP[i-1][1],DP[i-1][0])+T[i][2];
  }
  printf("%d",maxi(DP[n][0],maxi(DP[n][1],DP[n][2])));

  return 0;
}


Measured memory_bytes: 4864
// compile in C++11. use -std=c++11.
#include <iostream>
#include <iomanip>
#include <vector>
#include <valarray>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <bitset>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <complex>
#include <string>
#include <sstream>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>

// these require C++11
#include <unordered_set>
#include <unordered_map>
#include <random>

using namespace std;

#define int long long

#define all(c) c.begin(), c.end()
#define repeat(i, n) for (int i = 0; i < static_cast<int>(n); i++)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x) 
#endif

typedef complex<double> point;

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
	int n;
	unsigned long long a[40];
	a[0]=1;
	a[1]=2;
	a[2]=4;
	for(int i=3;i<40;i++){
		a[i]=a[i-3]+a[i-2]+a[i-1];
	}
	while(cin>>n){
		if(n==0) break;
		cout<<(int)ceil((double)a[n-1]/3650.0)<<endl;
	}
    return 0;
}

Measured memory_bytes: 1196
#include <algorithm>
#include <cstdio>
#include <utility>

using namespace std;

int main(void) {
	int n;
	int d[100001];

	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%d", &d[i]);
	}

	sort(d, d + n);

	// for(int i = 0; i < n; i++) {
	// 	printf("%d ", d[i]);
	// }
	// putchar('\n');

	int result = 0;
	if(d[n / 2 - 1] == d[n / 2]) {
		result = 0;
	} else {
		result = d[n / 2] - d[n / 2 - 1];
	}

	printf("%d\n", result);

	return 0;
}

Measured memory_bytes: 512
use std::vec::Vec;
use std::cmp::max;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
    let (n, W) = {
        let v: Vec<usize> = read_vec();
        (v[0], v[1])
    };

    let mut bagage = Vec::new();
    for _ in 0..n {
        let v: Vec<usize> = read_vec();
        bagage.push((v[0], v[1]));
    }
    
    let mut bagage_0 = Vec::new();
    let mut bagage_1 = Vec::new();
    let mut bagage_2 = Vec::new();
    let mut bagage_3 = Vec::new();

    let base_weight = bagage[0].0;

    for &(w, v) in &bagage {
        if w == base_weight {
           bagage_0.push((w, v));
        } else if w == base_weight + 1 {
           bagage_1.push((w, v));
        } else if w == base_weight + 2 {
            bagage_2.push((w, v));
        } else {
            bagage_3.push((w, v));
        }
    }

    bagage_0.sort_by(|a, b| b.1.cmp(&a.1));
    bagage_1.sort_by(|a, b| b.1.cmp(&a.1));
    bagage_2.sort_by(|a, b| b.1.cmp(&a.1));
    bagage_3.sort_by(|a, b| b.1.cmp(&a.1));

    let mut ans = 0;
    let mut weight = 0;
    for i in 0..bagage_0.len()+1 {
        for j in 0..bagage_1.len()+1 {
            for k in 0..bagage_2.len()+1 {
                for l in 0..bagage_3.len()+1 {
                    let (w_0, v_0) = sum_by_index(&bagage_0, 0, i);
                    let (w_1, v_1) = sum_by_index(&bagage_1, 0, j);
                    let (w_2, v_2) = sum_by_index(&bagage_2, 0, k);
                    let (w_3, v_3) = sum_by_index(&bagage_3, 0, l);
                    if w_0 + w_1 + w_2 + w_3 <= W {
                       ans = max(ans, v_0+v_1+v_2+v_3);
                    }
                }
            }
        }
    }

    println!("{}", ans);
}

fn sum_by_index(v: &Vec<(usize, usize)>, start: usize, end: usize) -> (usize, usize) {
    let mut res = (0, 0);
    for i in start..end {
        res = (res.0 + v[i].0, res.1 + v[i].1);
    }

    res
}

Measured memory_bytes: 4352
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;
typedef pair<int, int> P;

int main() {
  int N, M; cin >> N >> M;
  vector<P> ps(M), ans(M);
  for (int i = 0; i < M; ++i) cin >> ps[i].first >> ps[i].second;
  sort(ps.begin(),ps.end());

  int cnt = 0, start = -1, end = -1;
  for (auto [s, e] : ps) {
    if (end <= s) {
      ++cnt;
      start = s, end = e;
    } else {
      start = s, end = min(e, end);
    }
  }
  cout << cnt << endl;
}


Measured memory_bytes: 4804
#include<iostream>
#include<vector>
#include<string>


using ll = long long;

int main(){
    ll x;
    std::cin >> x;
    ll base = 100;
    ll cnt = 0;
    while(base < x){
        base = base + (base * 0.01) / 1;
        cnt++;
    }
    std::cout << cnt << std::endl;
    return 0;
}


Measured memory_bytes: 3592
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <math.h>
#include <utility>
#include <set>
#include <map>
#include <cstring>
#include <cstdio>
#include <stack>
#define INF 1000000000
#define rep(i,n) for(int i =0;i<n;i++)
using namespace std;
typedef long long int ll;

char g[60][60];
pair<int, int> used[60][60];
int w,h;

void dfsf(int x, int y, int color){
    if(x<0 or x>=h or y<0 or y>=w)return;
    if(used[x][y].first!=0) return;
    used[x][y].first=color;
    dfsf(x+1, y, color);
    dfsf(x-1, y, color);
    dfsf(x, y+1, color);
    dfsf(x, y-1, color);
}
void dfss(int x, int y, int color){
    if(x<0 or x>=h or y<0 or y>=w)return;
    if(used[x][y].second!=0) return;
    used[x][y].second=color;
    dfss(x+1, y, color);
    dfss(x-1, y, color);
    dfss(x, y+1, color);
    dfss(x, y-1, color);
}


int main(){
    for(;;){
        cin >> w >> h;
        if(w==0)break;
        memset(used, 0, sizeof(used));
        rep(i,h){
            rep(j, w){
                cin >> g[i][j];
                if(g[i][j]!='.')used[i][j]={3,3};
            }
        }
        rep(i,h){
            rep(j, w){
                if(g[i][j]=='B'){
                    dfsf(i+1, j, 1);
                    dfsf(i-1, j, 1);
                    dfsf(i, j+1, 1);
                    dfsf(i, j-1, 1);
                }
                if(g[i][j]=='W'){
                    dfss(i+1, j, 1);
                    dfss(i-1, j, 1);
                    dfss(i, j+1, 1);
                    dfss(i, j-1, 1);
                }
            }
        }
        int ans1=0,ans2 = 0;
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                if (used[i][j].first==1 and used[i][j].second==0) {
                    ans1++;
                }
                if (used[i][j].first ==0 and used[i][j].second == 1) {
                    ans2++;
                }
            }
        }
        cout << ans1 <<" "<<ans2<<endl;
    }
}

Measured memory_bytes: 1272
n = int(input())
a = list(map(int, input().split()))
b = []
lst = [0] * n
for i, x in reversed(list(enumerate(a))):
  if sum(lst[i::i+1]) % 2 != x:
    lst[i] += 1
    b.append(i+1)
print(len(b))
if len(b) > 0:
  print(*reversed(b))

Measured memory_bytes: 32748
import sys 
import math

X = int(input())
#a = list(map(int, input().split(" ")))
a = [0 for i in range(X+1)]

a[1] = 1

for i in range(2,int(math.sqrt(X))+1):
    num = i*i
    while num <= X:
        a[num]=1
        num *= i

for i in range(1,X+1):
    if a[i] == 1:
        ans = i
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

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

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

	ll n, m;cin >> n >> m;
	ll sum = 0;
	vector<ll> v(m);
	REP(i, m)cin >> v[i];
	REP(i, m)sum += v[i];
	cout << ((n - sum >= 0) ? n - sum : -1) << endl;

	return 0;
}


Measured memory_bytes: 3244
# -*- coding: utf-8 -*-

import sys
from heapq import heapify, heappush, heappop

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

A1 = A[:N]
A2 = A[N:]
sm1 = sum(A1)
sm2 = sum(A2)
que1 = []
que2 = []
S = set()
for i, a in enumerate(A1):
    que1.append((a, i))
heapify(que1)
A2 = [(a, i) for i, a in enumerate(A2, N)]
A2.sort(reverse=1)
for a, i in A2[:N]:
    sm2 -= a
    S.add(i)
    que2.append((a, i))
heapify(que2)

ans = sm1 - sm2
for i in range(N, N*2):
    # 前半
    heappush(que1, (A[i], i))
    sm1 += A[i]
    a, _ = heappop(que1)
    sm1 -= a
    # 後半
    if i not in S:
        sm2 -= A[i]
        while 1:
            a, j = heappop(que2)
            S.remove(j)
            if j > i:
                sm2 += a
                break
    ans = max(ans, sm1 - sm2)
print(ans)


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

int main() {
  
  long min = 1000000000;
  long max = -1000000000;
  long sum = 0;
  long N;
  long temp;

  std::cin >> N;
  for(long i = 0; i < N; ++i) {
    std::cin >> temp;
    min = std::min(temp, min);
    max = std::max(temp, max);
    sum += temp;
  }

  std::cout << min << " " << max << " " << sum << std::endl;
  
  return 0;
}

Measured memory_bytes: 1164
#pragma GCC optimize("O3")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds; 

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define f first
#define s second
#define sz(x) ll(x.size())
#define endl '\n'
#define forn(i,n) for(int i=0;i<n;++i)
#define fore(i,l,r) for(int i=int(l);i<=int(r);++i)
#define rep(i,begin,end) for(__typeof(end) i=(begin);i!=(end);i++)
#define fill(a,value) memset(a,value,sizeof(a));
#define gcd(a,b) __gcd((a),(b))
#define watch1(x) cout << (x) << endl
#define watch2(x,y) cout << (x) << " " << (y) << endl
#define watch3(x,y,z) cout << (x) << " " << (y) << " " << (z) << endl
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define int long long
 
typedef long long ll;
typedef long double ld; 
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> oset;

// find_by_order(k) returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;

const int mod = 998244353;
const int inf = 9e18;
const int N = 1e5 + 5;

int p[N],q[N],r[N];
priority_queue<int> pq,s1,s2;

void solve(){
    int i,x,y,a,b,c,ans=0;
    cin>>x>>y>>a>>b>>c;
    for(i=1;i<=a;++i){
        cin>>p[i];
        s1.push(p[i]);
    }
    for(i=1;i<=b;++i){
        cin>>q[i];
        s2.push(q[i]);
    }
    for(i=1;i<=c;++i){
        cin>>r[i];
        pq.push(r[i]);
    }
    for(i=0;i<x;++i){
        pq.push(s1.top());
        s1.pop();
    }
    for(i=0;i<y;++i){
        pq.push(s2.top());
        s2.pop();
    }
    for(i=0;i<x+y;++i){
        ans+=pq.top();
        pq.pop();
    }
    cout<<ans;
}

signed main(){
    fastio;
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 10352
#import sys
#import math
#import numpy as np

'''a,b= map(int,input().split())'''
#a, b, c = [list(map(int, input().split())) for _ in range(3)]
#li0= [int(x) for x in input().split()]
#n,l= map(int, input().split())
#x = [list(map(int, input().split())) for _ in range(n)] 
n,b=map(int,input().split())
ans=100**4
x=[list(map(int,input().split())) for _ in range(n)]
for i in range(n):
  if x[i][1]<=b:
    ans=min(ans,x[i][0])
if ans==100**4:
  print('TLE')
else:
  print(ans)
    

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
#define rrep(i,n) for (int i = (n - 1);i >= 0;i--)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int odd = (n+1)/2;
    cout << fixed << setprecision(10) << (double)odd / n << endl;
}

Measured memory_bytes: 256
def s():
 import sys
 r=sys.stdin.readline
 I=float('inf')
 for e in iter(r,'0 0\n'):
  n,k=map(int,e.split())
  F=[[I]*-~n for _ in[0]*-~n]
  for i in range(1,n+1):F[i][i]=0
  for _ in[0]*k:
   f=r();g=map(int,f[2:].split())
   if'0'==f[0]:a,b=g;A=F[a][b];print([A,-1][A==I])
   else:
    c,d,e=g
    if e<F[c][d]:
     for i in range(2,n+1):
      for j in range(1,i):
       F[i][j]=F[j][i]=min(F[i][j],F[i][c]+e+F[d][j],F[i][d]+e+F[c][j])
if'__main__'==__name__:s()


Measured memory_bytes: 6244
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(b);i>(a);--i)
#define eper(i,a,b) for(int i=((int)(a));i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF 2000000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

int n;
vector<int> a;
int main() {
 ios::sync_with_stdio ( false );
 cin.tie ( 0 );
    cin >> n;
    rep(i, 0, n) {
        int x; cin >> x;
        a.pb(x);
    }
    bool flag = false;
    int cnt = 0, ans = 0;
    rep(i, 0, n-1) {
        if (flag && a[i] != a[i+1]) {
            ans += (cnt+1)/2;
            flag = false;
        } else if (!flag) cnt = 0;
        if (a[i] == a[i+1]) {
            flag = true;
            cnt++;
        }
    }
    if (flag) ans += (cnt+1)/2;
    cout << ans << endl;
    return 0;
}


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

int main() {
  int N;
  cin >> N;
  int Sn=0;
  int Ns=N;
  for(int i=0;i<10;i++){
    Sn+=Ns%10;
    Ns=Ns/10;
  }
  if(N%Sn==0)cout << "Yes";
  else cout << "No";
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

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

    vector<int> vx(N);
    int max = 0;
    for(int i = 0; i < N; i++){
        cin >> vx[i];
        if(max < vx[i]){
            max = vx[i];
        }
    }
    double diff = max;
    double half = max / 2.0;
    int min = 0;
    for(int i = 0; i < N; i++){
        if(vx[i] == max) continue;
        if(diff > abs(vx[i] - half)){
            min = vx[i];
            diff = abs(vx[i] - half);
        }
    }
    cout << max << " " << min << endl;

    return 0;
}


Measured memory_bytes: 640
#include <stdio.h>

int main()
{
	int N, K;
	scanf ("%d %d", &N, &K);

	long long a = 0;
	for (int k = K; k <= N+1; k++){
		long long l = 1ll * (k - 1) * k / 2;
		long long r = 1ll * (2 * N - (k - 1)) * k / 2;
		a = (a + r - l + 1) % 1000000007;
	}
	printf ("%lld\n", a);

	return 0;
}

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

using namespace std;

// Prioridade
typedef long long   ll;
typedef pair<ll,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for(int i = a; i < (b); i++)
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(),x.end()
#define MOD 1000000007
#define endl '\n'
#define mdc(a, b) (__gcd((a), (b)))
#define mmc(a, b) (((a)*(b))/__gcd((a), (b)))

// fim da Prioridade
int dp[100010][4];
int a[100200];
int b[100200];
int c[100200];
int n;
int k;
int solve(int i,int state){
	if(i == n){
		return 0;
	}
	if(dp[i][state] != -1){
		return dp[i][state];
	}
	int ans = 0;
	if(state == 0){
		ans = max(a[i] + solve(i+1,1),max(b[i] + solve(i+1,2),c[i] + solve(i+1,3)));
	}else if(state == 1){
		ans = max(0,max(b[i] + solve(i+1,2),c[i] + solve(i+1,3)));
	}else if(state == 2){
		ans = max(a[i] + solve(i+1,1),max(0,c[i] + solve(i+1,3)));
	}else if(state == 3){
		ans = max(a[i] + solve(i+1,1),max(b[i] + solve(i+1,2),0));
	}
	return dp[i][state] = ans;
}
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	cin >> n;

	memset(dp,-1,sizeof dp);
	REP(i,0,n){
		cin >> a[i] >> b[i] >> c[i];
	}
	cout << solve(0,0) << endl;
	return 0;
}


Measured memory_bytes: 10752
<?php
list($A, $B, $Q) = array_map("intval", explode(" ", trim(fgets(STDIN))));
for($i = 0; $i < $A; $i++){
    $aArray[] = intval(fgets(STDIN));
}
array_unshift($aArray, -10**18);
$aArray[] = 10**18;
for($i = 0; $i < $B; $i++){
    $bArray[] = intval(fgets(STDIN));
}
array_unshift($bArray, -10**18);
$bArray[] = 10**18;

for($i = 0; $i < $Q; $i++){
    $qArray[] = intval(fgets(STDIN));
}

foreach($qArray as $q){
    $min = 10**18;
    $a = bsl($aArray, $q);
    $b = bsl($bArray, $q);
    foreach([[[$aArray, $a], [$bArray,$b]], [[$bArray, $b], [$aArray,$a]]] as list(list($aa, $_a), list($bb, $_b))){
        foreach([$aa[$_a], $aa[$_a+1]] as $a1){
            $p3 = isset($bb[$_b]) ? $bb[$_b] : 10**12;
            $p4 = isset($bb[$_b+1]) ? $bb[$_b+1] : 10**12;
            $min = min($min, abs($q - $a1) + abs($a1 - $p3));
            $min = min($min, abs($q - $a1) + abs($a1 - $p4));
        }
    }
    printf("%d\n", $min);
}

//二分探索　target以下で最大の値の場所を返す
function bsl($nums, $target) {
    $size = count($nums);
    $min = 0; 
    $max = $size - 1;
    while(true){
        $center = floor(($min + $max) / 2);
        $centerValue = $nums[$center];
        if($target == $centerValue){
            return $center;
        }elseif($target > $centerValue){
            $min = $center + 1;
        }else{
            $max = $center;
        }
        if($min == $max){
            $center = floor(($min + $max) / 2);
            $centerValue = $nums[$center];
            if($centerValue == $target){
                return $center;
            }elseif($centerValue < $target){
                return $center;
            }else{
                return $center-1;
            }
        }
    }
}


Measured memory_bytes: 48372
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main()
{
	int A, B, C;
	int d;
	cin >> A >> B >> C;

	if (B / A >= C) d = C;
	else d = B / A;

	cout << d << endl;
}

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

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

  if((inin == 'a') ||(inin == 'b') ||(inin == 'c') ||(inin == 'd') ||(inin == 'e') ||(inin == 'f') ||(inin == 'g') ||(inin == 'h') ||(inin == 'i') ||(inin == 'j') ||(
  inin == 'k') ||(inin == 'l') ||(inin == 'm') ||(inin == 'n') ||(inin == 'o') ||(inin == 'p') ||(inin == 'q') ||(inin == 'r') ||(inin == 's') ||(
  inin == 't') ||(inin == 'u') ||(inin == 'v') ||(inin == 'w') ||(inin == 'x') ||(inin == 'y') ||(inin == 'z') ){
      cout << 'a' << endl;
  }

  else cout << 'A' << endl;


}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
signed main(){
	int a,b,c,d,e,f,g,h,i;
	cin>>a>>b>>c>>d>>e>>f>>g>>h>>i;
	int j=a-b,k=b-c;
	if(j==d-e&&k==e-f&&j==g-h&&k==h-i)puts("Yes");
	else puts("No");
	return 0;
}


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

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

  vector<int> D(K);
  for (int i = 0; i < K; i++)
  {
    cin >> D.at(i);
  }

  //計算量がそこまで大きくないので見つかるまで全探査
  int ans = N;
  while (true)
  {
    string strN = to_string(ans);
    bool includedHateNum = false;
    for (int i = 0; i < D.size(); i++)
    {
      if (count(strN.begin(), strN.end(), '0' + D.at(i)))
      {
        ans++;
        includedHateNum = true;
      }
    }
    if (!includedHateNum)
    {
      break;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using PII = pair<int, int>;
random_device rnd;
mt19937 mt(rnd());

const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 1e9 + 7;
int main()
{
    int h, w, a, b;
    cin >> h >> w >> a >> b;
    rep(i, h - b)
    {
        rep(j, w)
        {
            if (j < w - a)
                cout << 0;
            else
                cout << 1;
        }
        cout << endl;
    }
    rep(i, b)
    {
        rep(j, w)
        {
            if (j < w - a)
                cout << 1;
            else
                cout << 0;
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 1280
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
	int N;
	cin>>N;
	long long a[301][301];
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			cin>>a[i][j];
	for(int i=1;i<=N;i++)
	{
		for(int j=i+1;j<=N;j++)
		{
			for(int k=j+1;k<=N;k++)
			{
				if(a[i][j]+a[i][k]==a[j][k])
					a[k][j]=0;
				else if(a[i][j]+a[j][k]==a[i][k])
					a[k][i]=0;
				else if(a[i][k]+a[j][k]==a[i][j])
					a[j][i]=0;
				 if((a[i][j]+a[i][k]<a[j][k])||(a[i][j]+a[j][k]<a[i][k])||(a[i][k]+a[j][k]<a[i][j]))
				{
					cout<<"-1"<<endl;
					return 0;
				}	
			}
		}
	}
	long long sum=0;
	for(int i=1;i<=N;i++)
		for(int j=1;j<i;j++)
			sum+=a[i][j];
	cout<<sum<<endl;		
	return 0;
}

Measured memory_bytes: 896