akhauriyash/Code-Regression huggingface dataset:
n = gets.chomp.to_i
arr = gets.split.map(&:to_i)
arr_odd = arr.sort.reverse.select.with_index{|e, i| i % 2 == 0}
arr_even = arr.sort.reverse.select.with_index{|e, i| i % 2 == 1}
puts arr_odd.inject{|sum, n| sum + n} - arr_even.inject{|sum, n| sum + n}

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std; 
int main(){
  int x,t,index,n,i,a;
  float Min,y;
  cin>>n>>t>>a>>y;
  Min = abs(a - t + 0.006*y);
  index = 1;
  for(i=2;i<=n;i++){
    cin>>y;
    if(Min > abs(a - t + 0.006*y) ){
		Min = abs(a - t + 0.006*y);
      index = i;
    }
  }
  cout<<index;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <utility>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <istream>
#include <ostream>

#include <cstdlib>
#include <cmath>
#include <cstdio>

using namespace std;

#define fi first
#define se second
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define rep(i,n) for(ll i=0; i < (n); ++i)
#define rrep(i,n) for(ll i=((n)-1); i >= 0; --i)

#define OPLT(T) bool operator<(const T & lop_, const T & rop_)
#define OPEQ(T) bool operator==(const T & lop_, const T & rop_)

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

istream& operator>>(istream& istr, __float128& obj) { double d; istr >> d; obj = d; return istr; };
ostream& operator<<(ostream& ostr, __float128& obj) { ostr << static_cast<double>(obj); return ostr; };

int f(ll n) {
	int res = 0;
	while(n) {res++; n/=10;}
	return max(res,1);
}

int F(ll A, ll B) {
	return max(f(A),f(B));
}

int main() {
	ll N; cin >> N;
	int res = f(N);
	for(ll i = 1; i*i <= N; i++) {
		if(N%i == 0) {
			res = min(res,F(i,N/i));
		}
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 256
s = input()
t = input()
ls = len(s)
lt = len(t)
sl = [0]*(ls+1)
tl = [0]*(lt+1)
for i in range(ls):
  if s[i] == "A":
    sl[i+1] = sl[i] + 1
  else:
    sl[i+1] = sl[i] + 2
for i in range(lt):
  if t[i] == "A":
    tl[i+1] = tl[i] + 1
  else:
    tl[i+1] = tl[i] + 2
for _ in range(int(input())):
  a,b,c,d = map(int, input().split())
  if (sl[b]-tl[d]-sl[a-1]+tl[c-1])%3 == 0:
    print("YES")
  else:
    print("NO")

Measured memory_bytes: 13460
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;
#define N 100010
ll n,a[N];
vector<int> v;
int main(){
    cin>>n;
    ll esum=0,osum=0;
    lol(i,n){
	cin>>a[i];
	if((i+1)%2==0)esum+=max((ll)0,a[i]);
	else osum+=max((ll)0,a[i]);
    }
    if(max(esum,osum)==0){
	ll maxi=-(ll)mod*(ll)mod,p=0;
	lol(i,n){
	    if(maxi<a[i]){
		maxi=a[i];
		p=i;
	    }
	}
	cout<<maxi<<endl;
	cout<<n-1<<endl;
	for(int i=n-1;i>p;i--)cout<<i+1<<endl;
	lol(i,p)cout<<1<<endl;
	return 0;
    }
    
    cout<<max(esum,osum)<<endl;
    int siz=n-1;
    if(esum>osum){
	v.push_back(1);
	siz--;
	for(int i=0;i<n-1;i++)a[i]=a[i+1];
	n--;
    }
    int first=0;
    for(int i=0;i<n;i+=2)if(a[i]>0){first=i;break;}
    lol(i,first){
	v.push_back(1);
	siz--;
    }
    for(int i=0;i<n-first;i++)a[i]=a[i+first];
    n-=first;
    
    int last=0;
    for(int i=0;i<n;i+=2)if(a[i]>0)last=i;
    for(int i=n;i>last+1;i--){
	v.push_back(i);
	siz--;
    }
    n=last+1;
    //lol(i,n)cout<<a[i]<<" ";cout<<endl;
    int t=1,len=0,dir=0;
    for(int i=0;i<n;i+=2){
	//cout<<"&"<<i<<" "<<t<<endl;
	string s="nan";
	if(a[i]>0&&dir!=1)s="minusend";
	if(a[i]<=0&&dir!=-1)s="plusend";
	if(s=="minusend"){
	    dir=1;
	    lol(k,len){
		v.push_back(t);
		siz-=2;
	    }
	    //cout<<"me"<<" "<<i<<" "<<t<<" "<<len<<endl;
	    len=1,t++;
	}
	if(s=="plusend"){
	    dir=-1;
	    lol(k,len-1){
		v.push_back(t);
		siz-=2;
	    }
	    //cout<<"pe"<<" "<<i<<" "<<t<<" "<<len<<endl;
	    len=1,t++;
	}
	if(s=="nan")len++;
    }
    lol(i,siz/2)v.push_back(2);
    
    cout<<v.size()<<endl;
    lol(i,v.size())cout<<v[i]<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#define DIM 200005
#define mod 1000000007
using namespace std;
int n, i, x, sol, nr;
int ind[DIM], niv[DIM], pt[DIM], num[DIM];
vector<int> v[DIM];
struct str{
    int d0, d1, d2;
};
vector<str> w[DIM];
void dfs(int nod){
    if(v[nod].size() == 0){
        nr++;
        ind[nod] = nr;
        w[nr].push_back( {1, 1, 0} );
        return;
    }
    int i, j, vecin, x, maxim = 0;
    for(i = 0; i < v[nod].size(); i++){
        niv[ v[nod][i] ] = niv[nod] + 1;
        dfs(v[nod][i]);
    }
    ind[nod] = ind[ v[nod][0] ];
    for(i = 1; i < v[nod].size(); i++){
        vecin = v[nod][i];
        if(w[ ind[vecin] ].size() > w[ ind[nod] ].size()){
            ind[nod] = ind[vecin];
        }
    }
    w[ ind[nod] ].push_back( {1, 1, 0} );
    str a, b;
    for(i = 0; i < v[nod].size(); i++){
        vecin = v[nod][i];
        if(ind[vecin] == ind[nod]){
            continue;
        }
        x = w[ ind[nod] ].size() - 1;
        if(w[ ind[vecin] ].size() > maxim){
            maxim = w[ ind[vecin] ].size();
        }
        for(j = w[ ind[vecin] ].size() - 1; j >= 0; j--){
            x--;
            b = w[ ind[vecin] ][j];
            a = w[ ind[nod] ][x];
            w[ ind[nod] ][x].d0 = a.d0 * 1LL * b.d0 % mod;
            w[ ind[nod] ][x].d1 = (a.d1 * 1LL * b.d0 + a.d0 * 1LL * b.d1) % mod;
            w[ ind[nod] ][x].d2 = (a.d1 * 1LL * b.d1 + a.d2 * 1LL * b.d1 + a.d2 * 1LL * b.d0)% mod;
        }
    }
    if(nod == 1){
        int abc = 0;
    }
    for(j = w[ ind[nod] ].size() - 2; j >= 0; j--){
        if(maxim == 0){
            break;
        }
        w[ ind[nod] ][j].d0 = (w[ ind[nod] ][j].d0 + w[ ind[nod] ][j].d2) % mod;
        w[ ind[nod] ][j].d2 = 0;
        maxim--;
    }
}
int main(){
    cin>> n;
    n++;
    for(i = 2; i <= n; i++){
        cin>> x;
        v[x + 1].push_back(i);
    }
    dfs(1);
    x = w[ ind[1] ].size();
    pt[0] = 1;
    for(i = 1; i <= n; i++){
        num[ niv[i] ]++;
        pt[i] = pt[i - 1] * 2 % mod;
    }
    for(i = 0; i < w[ ind[1] ].size(); i++){
        x--;
        sol = (sol + w[ ind[1] ][i].d1 * 1LL * pt[n - num[x] ]) % mod;
    }
    cout<< sol;
}


Measured memory_bytes: 44532
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
ans=sum(B)
for i in range(1,N):
    if A[i-1]+1==A[i]:
        ans+=C[A[i]-2]
print(ans)
    

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define lol long long
template<class A,class B>inline bool chmax(A &a,const B &b){return(b>a&&(a=b,true));}
template<class A,class B>inline bool chmin(A &a,const B &b){return(b<a&&(a=b,true));}
using namespace std;
lol mod=1e9+7;
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;cin >>n;
  vector<lol> a(n);
  for(int i=0;i<n;i++) cin >>a[i];
  int con=0,mi=mod;
  lol ans=0;
  for(int i=0;i<n;i++){
    if(a[i]<0) con++;
    chmin(mi,abs(a[i]));
    ans+=abs(a[i]);
  }
  cout <<ans-(con&1?(mi+mi):0)<<'\n';
  return (0);
}

Measured memory_bytes: 3872
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <float.h>
#include <iomanip>
#include <iostream>
using namespace std;


int main(){
    
    string S;
    bool f=0;
    cin >> S;

    for(int i=0;i<S.length();i++){
        if(i%2!=0){
            //偶数番目
            if(S[i]=='R'){
                f=1;
                break;
            }
        }else{
            //奇数番目
            if(S[i]=='L'){
                f=1;
                break;
            }
        }

    }

    if(f==1){
        cout << "No";
    }else{
        cout <<"Yes";
    }

    return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = pow(10, 9) + 7;
//const int MOD = 998244353;
//const int MOD = ;
int mod(int A, int M) {return (A % M + M) % M;}
const int INF = 1LL << 60;
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
template <class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}
int myctoi(char C) {return C - 48;}
char myitoc(int N) {return '0' + N;}

signed main()
{
  map<string, int> mp;
  
  int N;
  cin >> N;
  for (int i = 0; i < N; i++)
  {
    string s;
    cin >> s;
    mp[s]++;
  }
  int M;
  cin >> M;
  for (int i = 0; i < M; i++)
  {
    string t;
    cin >> t;
    mp[t]--;
  }
  
  int ans = 0;
  for (auto it = mp.begin(); it != mp.end(); it++)
  {
    chmax(ans, it->second);
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
def menagerie(N: int, s: str) -> str:
    # Sheep: True, Wolf: False

    # 0 番目と 1 番目の道具ぶつの組み合わせだけ全探索。
    # その 2 頭が決まればあとは一意に決まる。
    is_sheeps = [[None] * N for _ in range(4)]

    # SS
    is_sheeps[0][:2] = True, True
    # SW
    is_sheeps[1][:2] = True, False
    # WS
    is_sheeps[2][:2] = False, True
    # WW
    is_sheeps[3][:2] = False, False

    for n in range(1, N):
        for is_sheep in is_sheeps:
            if (s[n] == 'o') == is_sheep[n]:
                # n 番目の動物が羊で発言が 'o'、あるいは
                # 狼で発言が 'x' なら n 番目の両隣は同じ動物
                is_sheep[(n + 1) % N] = is_sheep[n - 1]
            else:
                # n 番目の動物が羊で発言が 'x'、あるいは
                # 狼で発言が 'o' なら n 番目の両隣は違う動物
                is_sheep[(n + 1) % N] = not is_sheep[n - 1]

    for i, is_sheep in enumerate(is_sheeps):
        if is_sheep[0] != (i // 2 == 0):
            # n-1 番目の動物の発言を検証したときに、
            # 先頭の動物が仮定と矛盾する。
            continue
        if ((s[0] == 'o') == is_sheep[0]) != (is_sheep[1] == is_sheep[-1]):
            # 先頭の動物の発言を検証したときに、
            # 先頭の動物が仮定と矛盾している。
            continue
        return ''.join('S' if b else 'W' for b in is_sheep)

    return '-1'


if __name__ == "__main__":
    N = int(input())
    s = input()
    ans = menagerie(N, s)
    print(ans)


Measured memory_bytes: 7156
use List::Util qw/max/;

chomp (my $s = <STDIN>);
chomp (my $t = <STDIN>);
my @s = sort {$a cmp $b} split('', $s);
my @t = sort {$b cmp $a} split('', $t);
my $f = 0;
for my $i (0..max($#s, $#t)) {
  if (!$s[$i]) {
    $f = 1;
    last;
  } elsif (!$t[$i]) {
    last;
  } elsif ($s[$i] gt $t[$i]) {
    last;
  } elsif ($s[$i] lt $t[$i]) {
    $f = 1;
    last;
  }
}
print ($f ? "Yes\n" : "No\n");

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <time.h>
#define int long long
#define endl '\n'
#define INF 1000000000000000000
#define EPS 1e-10
#define PI 3.141592653589793238
#define all(a) a.begin(),a.end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define fi first
#define se second
#define pb push_back
#define double long double
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
typedef complex<double> com;
template<class T, class S> bool chmax(T &a, const S &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class S> bool chmin(T &a, const S &b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }


signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	//modcalc();

	int n;
	cin >> n;
	vector<int> a(n), b(n), c(n), d(n);
	rep(i, n) cin >> a[i] >> b[i];
	rep(i, n) cin >> c[i] >> d[i];
	vector<PP> p;
	rep(i, n) {
		p.pb(PP(a[i], P(b[i], 0)));
		p.pb(PP(c[i], P(d[i], 1)));
	}
	sort(all(p)); reverse(all(p));
	int ans = 0;
	vector<PP> vec;
	rep(i, 2 * n) {
		int px = p[i].first;
		int py = p[i].second.first;
		int pz = p[i].second.second;
		if (pz == 0) {
			int ny = INF;
			int idx = -1;
			for (int j = 0; j < vec.size(); j++) {
				if (vec[j].second.second&& px < vec[j].first&&py < vec[j].second.first) {
					if (chmin(ny, vec[j].second.first)) idx = j;
				}
			}
			if (idx != -1) {
				ans++;
				vec[idx].second.second = 0;
			}
		}
		else {
			vec.pb(PP(px, P(py, 1)));
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
A = list(map(int, input().split()))
def answer(N: int, M: int, A: list) -> int:
    homework_days = 0
    for i in range(0, M):
        homework_days += int(A[i])
        i += 1
    if homework_days <= N:
        return N - homework_days
    else:
        return -1

print(answer(N, M, A))

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

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

#define pow CHANGETHENAMESTUPID

using namespace std;

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

void load() {
	int k, n;
	scanf("%d%d", &k, &n);
	int a[n];
	FOR(i, n) scanf("%d", a + i);
	int maxi = 0;
	for (int i = 1; i < n; i++) maxi = max(maxi, a[i] - a[i-1]);
	maxi = max(maxi, (k - a[n-1]) + a[0]);
	printf("%d\n", k - maxi);
}

void solve() {

}

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


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

// @author: pashka

int main() {
    ios::sync_with_stdio(false);
    
    string s;
    cin >> s;
    int i = 0, j = s.size() - 1;
    int res = 0;
    while (i < j) {
        if (s[i] != s[j]) res++;
        i++; j--;
    }
    cout << res;

    return 0;
}

Measured memory_bytes: 384
N, K = map(int, input().split(" "))
routs = {}
location = [0 for i in range(N + 1)]
tereporter = list(map(int, input().split()))
for i in range(N):
  routs[i] = tereporter[i] - 1
present_location = 0
n = 0
for i in range(K):
  n += 1
  present_location = routs[present_location]
  if location[present_location] == 0:
    location[present_location] = n
  else:
    loop = n - location[present_location]
    if (K - location[present_location]) % loop == 0:
      break
    else:
      for i in range((K - location[present_location]) % loop):
        present_location = routs[present_location]
      break
print(present_location + 1)

Measured memory_bytes: 47460
#include "bits/stdc++.h"
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long int
#define int ll
// #define double long double
//#define slld(t) scanf("%lld",&t)
//#define sd(t) scanf("%d",&t)
//#define pd(t) printf("%d\n",t)
//#define plld(t) printf("%lld\n",t)
#define vec vector < int >
#define vecp vector < pair < int , int > >
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define debug(x)   cerr<<#x<<": "<<x<<endl
#define pii pair < int , int >
#define pll pair < ll , ll > 
#define debug(x)   cerr<<#x<<": "<<x<<endl
#define mod  1000000007
#define N   100005
#define MAX 300005
#define mod1 1000000007
#define mod2 998244353
#define bitcnt __builtin_popcountll
#define PI acos(-1)
//#define endl "\n"
#define inf 1e+15
int n;
int dp[100005][2];
vec v;
int get(int idx,int t){
	if(idx>= n) return 1;
	if(dp[idx][t]!= -1)
		return dp[idx][t];
	int res = 0;
	if(t == 1 && v[idx]==1){
		res += get(idx+1 , 0 );      // 00 
        res += get(idx+1 , 1);       // 01
        res += get(idx+1 , 1);       // 10
        res %= mod;
	}
	else if(t==1 && v[idx] == 0){
		res += get(idx+1,1);
		res%=mod;          // 00
	}
	else{
		res += get(idx+1 , 0) * 3ll;
		res %= mod;

	}

	dp[idx][t]=res;
	return res;
}
signed main(){
  fast;
  string s;
  cin>>s;
  n = s.length();
  memset(dp , -1 , sizeof(dp));
  for(int i=0;i<n;i++)
  	  v.pb((int)s[i]-'0');

  int ans = get(0,1);
  cout<<ans<<endl;
}
  


Measured memory_bytes: 7492
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cmath>
#include <map>
using namespace std;
#define MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int main()
{
	char s[101];
	scanf("%s", &s);
	int a = 0;
	for (int i = 0; s[i]; ++i) {
		if (a == 0 && s[i] == 'C') ++a;
		if (a == 1 && s[i] == 'F') ++a;
	}
	puts(a == 2 ? "Yes" : "No");
	return 0;
}


Measured memory_bytes: 384
#include <iostream>

int Length_Rest(int x, int y){
    return 2*x + 2*y;
}

int Area_Rect(int x, int y){
    return x*y;
}

int main(int argc, const char * argv[]) {
    int a;
    int b;
    std::cin >> a >> b;
    std::cout << Area_Rect(a,b)<< " " << Length_Rest(a,b) << std::endl;
    return 0;
}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	string n; cin>>n;
	int r=0,b=0;
	for(auto&i:n)if(i=='0')++r;else++b;
	cout<<min(r,b)*2<<"\n"s;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;
LL p = 1000000007ll;

int main(void)
{
  LL x,a;
  cin >> x >> a;
  cout << (x<a?0:10) << endl;
  return 0;
}


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

int main(void){
    // 入力
    long long n,k;
    cin >> n >> k;
    string s;
    cin >> s;

    // 初期状態での幸福な人数を数える
    long long happy=0;
    for(int i=0; i<n; i++){
        if(s[i]=='L' && s[i-1]=='L' && i-1>=0){
            happy+=1;
        }
        else if(s[i]=='R' && s[i+1]=='R' && i+1<n){
            happy+=1;
        }
    }

    //幸福になるのは最大n-1人
    for(int i=0; i<k; i++){
        if(happy+1>=n){
            continue; 
        }
        // 左L or 右Rの時で+1したい時(最後)
        else if(happy==n-2){
            happy+=1;

        }
        else{
            happy+=2;
        }
    }

    cout<<happy;

    return 0;
}

Measured memory_bytes: 512
#include<iostream>
using namespace std;
const static int INF = 100000000;
int main(){
    int n,m;
    cin>>n>>m;
    int a[m],b[m],c[m];
    for(int i = 0; i < m; i++)
    {
        cin>>a[i]>>b[i]>>c[i];
        a[i]--;b[i]--;
    }

    int dist[n][n];

    for(int i=0;i<n;i++)for(int j=0;j<n;j++)dist[i][j]=(i==j?0:INF);

    for(int i=0;i<m;i++){
        dist[a[i]][b[i]]=min(dist[a[i]][b[i]],c[i]);
        dist[b[i]][a[i]]=min(dist[b[i]][a[i]],c[i]);
    }

    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }

    int  ans=0;
    for(int i=0;i<m;i++)if(dist[a[i]][b[i]]<c[i])ans++;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <ios>
#include <iomanip>
#include <algorithm>
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP2(i, m, n) for (int i = (m); i < (int)(n); ++i)
#define REPR(i, n) for (int i = (n)-1; i >= 0; --i)
#define REPR2(i, m, n) for (int i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a) sort(ALL(a), greater<int>())
#define REVERSE(a) reverse(ALL(a))
#define bit_search(bit, n) REP(bit, 1<<(n))
#define bit_check(bit, i) ((bit>>(i)) & 1)
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) lower_bound(ALL(a), (x)) - a.begin()
#define bisect_right(a, x) upper_bound(ALL(a), (x)) - a.begin()
#define INPUT(a) REP(i, a.size()) cin >> a[i];
#define INPUTP(a) REP(i, a.size()) cin >> a[i].first >> a[i].second;
#define OUTPUT_PERMUTATION(n) do{VI v(n); iota(ALL(v), 1); do{REPx(x, v) cout << x << " "; ENDL} while(next_permutation(ALL(v)));} while(0);
#define MAKE_PERMUTATION(n) do{VVI a(fact(n), VI(n)); int idx = 0; VI v(n); iota(ALL(v), 1); do{REP(i, n) a[idx][i] = v[i]; idx++; PER = a;} while(next_permutation(ALL(v)));} while(0); // int fact(), VVI PERを宣言しておく
#define ENDL cout << endl;
using namespace std;
using LL = long long;
using LD = long double;
using PII = pair<int, int>;
using VPII = vector<PII>;
using PLL = pair<LL, LL>;
using VPLL = vector<PLL>;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VC = vector<char>;
using VS = vector<string>;
using VB = vector<bool>;
using VD = vector<double>;
const int INF = 1e9;
const LL MOD = 1e9 + 7;

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

void END(){cout << 1 << endl; exit(0);}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int d, g;
  cin >> d >> g;
  VI p(d), c(d);
  REP(i, d) cin >> p[i] >> c[i];
  int ans = INF;
  bit_search(bit, d)
  {
    int score = 0;
    int ct = 0;
    REP(i, d)
    {
      if (bit_check(bit, i))
      {
        score += 100*(i+1)*p[i] + c[i];
        ct += p[i];
      }
    }
    if (score < g)
    {
      REPR(i, d)
      {
        if (score >= g) break;
        if (!bit_check(bit, i))
        {
          int rest = g-score;
          int q = (rest-1)/(100*(i+1)) + 1;
          if (q <= p[i]-1)
          {
            score = g;
            ct += q;
          }
          else
          {
            score += (p[i]-1)*100*(i+1);
            ct += p[i]-1;
          }
        }
      }
    }
    if (score >= g) chmin(ans, ct);
  }
  cout << ans;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream> 
#include<unordered_map>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max() >> 2;
const ll linf = numeric_limits<ll>::max() >> 2;
const ull ulinf = numeric_limits<ull>::max() >> 2;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define umap(i,j) unordered_map<i,j>
#define P(p) cout<<(p)<<endl
#define PS(p) cout<<(p)<< " "
#define PN cout << endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i = (n-1); i >= (int)(m); i--)
#define inrep(n,a) for(int i = 0; i < (int)(n); i++)cin >> a[i];
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v,c) sort(v.begin(), v.end(), greater<c>()) 
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - (a)) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - (a)) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

/*
ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
*/

/*
vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}
*/

/*
ll ncr[100][100];
ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

ll npr[100][100]={};
ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

ll nHr(int n,int r){ret nCr(n+r-1,r);}
*/

///////////////////////////////////////////////////////////////////////////



int main(){
    rep(i,0,5){
	int a;
	cin >> a;
	if(a == 0){
	    P(i+1);
	    ret 0;
	}
    }
    return  0;
}


Measured memory_bytes: 3600
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>

using namespace std;

typedef long long ll;

typedef pair<ll,ll> P;
#define X first
#define Y second

const int N = 4096;
vector<vector<int> > cw(N,vector<int>(N,0));
vector<vector<int> > cb(N,vector<int>(N,0));


int calc_cw(int a,int b,int c,int d) {
	a--; b--; c--; d--;
	int res = cw[c][d];
	if(a>=0&&b>=0) res += cw[a][b];
	if(a>=0) res -= cw[a][d];
	if(b>=0) res -= cw[c][b];
	// cout << a << " " << b << " " << c << " " << d << " " << res <<endl;
	return res;
}

int calc_cb(int a,int b,int c,int d) {
	a--; b--; c--; d--;
	int res = cb[c][d];
	if(a>=0&&b>=0) res += cb[a][b];
	if(a>=0) res -= cb[a][d];
	if(b>=0) res -= cb[c][b];
	// cout << a << " " << b << " " << c << " " << d << " " << res <<endl;
	return res;
}

void go() {
	int n,k;
	cin >> n >> k;
	for(int i = 0; i < n; i++) {
		int x,y;
		string c;
		cin >> x >> y >> c;
		x %= 2*k;
		y %= 2*k;
		if(c[0]=='B') {
			cb[x][y]++;
			cb[x+2*k][y]++;
			cb[x][y+2*k]++;
			cb[x+2*k][y+2*k]++;
		} else {
			cw[x][y]++;
			cw[x+2*k][y]++;
			cw[x][y+2*k]++;
			cw[x+2*k][y+2*k]++;
		}

	}
	for(int i = 0; i < 3*k; i++) {
		for(int j = 0; j < 3*k; j++) {
			if(i>0&&j>0) {
				cw[i][j] -= cw[i-1][j-1];
				cb[i][j] -= cb[i-1][j-1];
			}
			if(i>0) {
				cw[i][j] += cw[i-1][j];
				cb[i][j] += cb[i-1][j];
			}
			if(j>0) {
				cw[i][j] += cw[i][j-1];
				cb[i][j] += cb[i][j-1];
			}
		}
	}

	int best = 0;
	for(int i = 0; i < k; i++) {
		for(int j = 0; j < k; j++) {
			int res = 0;
			res += calc_cw(i,j,i+k,j+k);
			res += calc_cw(i+k,j+k,i+2*k,j+2*k);
			res += calc_cb(i,j+k,i+k,j+2*k);
			res += calc_cb(i+k,j,i+2*k,j+k);
			// cout << res << endl;
			best = max(res,best);
			res = 0;
			res += calc_cb(i,j,i+k,j+k);
			res += calc_cb(i+k,j+k,i+2*k,j+2*k);
			res += calc_cw(i,j+k,i+k,j+2*k);
			res += calc_cw(i+k,j,i+2*k,j+k);
			best = max(res,best);
			// cout << res << endl;
		}
	}
	cout << best << endl;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	// int t; cin >> t; for(;t--;)
	go();
	return 0;
}



Measured memory_bytes: 131712
#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
 
const ll mod = 1e9+7;
const double pi = acos(-1);

int n,t,j,i,k;
int m, c[12][12];
int f[11],bc[11];
int dp[12][12];


int main(){
	memset(f, 0, sizeof f);
	scanf("%d %d", &n, &m);
	for(i=0;i<10;i++){
		for(j=0;j<10;j++){
			scanf("%d", c[i]+j);
			dp[i][j] = c[i][j];
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			scanf("%d", &t);
			if(t>=0)
				f[t]++;
		}
	}
	newload:
	for(i=0;i<10;i++){
		for(j=0;j<10;j++){
			for(k=0;k<10;k++){
				if(dp[i][j] > dp[i][k]+dp[k][j]){
					dp[i][j] = dp[i][k]+dp[k][j];
					goto newload;
				}
			}
		}
	}
	int ans =0;
	for(i=0;i<10;i++)
		ans += f[i]*dp[i][1];
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int N;
	scanf("%d",&N);
	if(N==1)
	printf("1");
	if(1<N&&N<4)
	printf("2");
	if(3<N&&N<8)
	printf("4");
	if(7<N&&N<16)
	printf("8");
	if(15<N&&N<32)
	printf("16");
	if(31<N&&N<64)
	printf("32");
	if(63<N&&N<101)
	printf("64");
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main () 
{
    int day[3];
    int tday = 0;
    
    scanf("%s", day);
  
    if(strcmp(day,"SUN") == 0)
    {
        tday = 7;
    }
    else if(strcmp(day,"MON") == 0) 
    {
        tday = 6;
    } 
    else if(strcmp(day,"TUE") == 0) 
    {
        tday = 5;
    } 
    else if(strcmp(day,"WED") == 0)
    {
        tday = 4;
    } 
    else if(strcmp(day,"THU") == 0)
    {
        tday = 3;
    }
    else if (strcmp(day,"FRI") == 0)
    {
        tday = 2;
    }
    else if(strcmp(day,"SAT") == 0)
    {
        tday = 1;
    }
    
    printf("%d", tday);

    
  
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int count[4][3][10]={0};
  for(int i = 0;i<n;i++){
      int a, b, c, d;
      cin >> a >>b >> c >> d;
      count[a-1][b-1][c-1] += d;
      if(count[a-1][b-1][c-1]>9)
        count[a-1][b-1][c-1] = 9;
      else if(count[a-1][b-1][c-1] < 0){
        count[a-1][b-1][c-1] = 0;
      }
  }
  for(int i=0;i<4;i++){
      for(int j=0;j<3;j++){
          for(int k = 0; k<10;k++){
              cout<< ' ' << count[i][j][k] ;
          }
          cout << endl;
      }
    if(i!=3)
      cout << "####################" << endl;
  }
}


Measured memory_bytes: 3096
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <iomanip>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<long double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

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

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }
#define INF 1LL<<60

class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)
    set<ll> par_set;

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) {
            par[i] = i; // 初期では親は自分自身
            par_set.insert(i);
        }
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
        for (ll i = 0; i < sz_; ++i) {
            par[i] = i; // 初期では親は自分自身
            par_set.insert(i);
        }
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        par_set.erase(y);
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(M), B(M), ans(M);
    REP(i, M) {
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }
    reverse(ALL(A));
    reverse(ALL(B));

    auto union_find = UnionFind(N);
    ll tmp = 0; // merge前の連結成分ないの個数
    REP(i, M) {
        ans[i] = N * (N-1) / 2 - tmp;
        bool flag = (union_find.root(A[i]) != union_find.root(B[i]));
        if(flag) {
            tmp -= union_find.siz[union_find.root(A[i])] * (union_find.siz[union_find.root(A[i])] - 1) / 2;
            tmp -= union_find.siz[union_find.root(B[i])] * (union_find.siz[union_find.root(B[i])] - 1) / 2;
            union_find.merge(A[i], B[i]);
            tmp += union_find.siz[union_find.root(A[i])] * (union_find.siz[union_find.root(A[i])] - 1) / 2;
        }
    }

    reverse(ALL(ans));
    REP(i, M) {
        cout << ans[i] << endl;
    }
    return 0;
}

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

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

    char mem = 'N';
    char box;
    int counter =0;

    for ( int i; i<n; i++) {
        cin >> box;
        if ( mem != box) {
            counter++;
        }
        mem =box;
    }

    cout << counter << endl;


}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define repr(i, a, b) for(ll i = (a); i < (b); i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
const ll MOD = 1000000007;
const ll INF = 100000000000000000LL;
inline ll GCD(ll a, ll b){ return b?GCD(b, a % b):a; }
inline ll LCM(ll a, ll b){ return a/GCD(a, b)*b; }
inline ll powint(ll x, ll y){ ll r=1; while(y){ if(y&1) r*=x; x*=x; y>>=1; } return r; }
inline ll powmod(ll x, ll y, ll m = MOD){ ll r=1; while(y){ if(y&1) r*=x; x*=x; r%=m; x%=m; y>>=1; } return r; }
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; }
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif

ll cnt[100010];

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n;
    cin >> n;
    vll a(n);
    rep(i, n){
        cin >> a[i];
        cnt[a[i]]++;
    }
    ll ans = 0;
    repr(i, 1, 99999){
        chmax(ans, cnt[i-1]+cnt[i]+cnt[i+1]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>

using namespace std;
int main(){
 int a,b,c;
 cin >>a>>b>>c;

if(a<b){
  if(b<c){cout<<a<<" "<<b<<" "<<c<<endl;}else{if(c<a){cout<<c<<" "<<a<<" "<<b<<endl;}else{cout<<a<<" "<<c<<" "<<b<<endl;};};}

if(a>b){
  if(b>c){cout<<c<<" "<<b<<" "<<a<<endl;}else{if(c<a){cout<<b<<" "<<c<<" "<<a<<endl;}else{cout<<b<<" "<<a<<" "<<c<<endl;};};}




return 0;
}


Measured memory_bytes: 3092
from collections import defaultdict
def main():
    N = int( input())
    d = defaultdict( int)
    for i in range(2, int(N**(1/2))+1):
        while N%i == 0:
            d[i] += 1
            N //= i
    if N > 1:
        d[N] += 1
    ans = 0
    for key in d:
        for i in range(1, 100):
            if i*(i+1)//2 > d[key]:
                ans += i-1
                break
    print(ans)
if __name__ == '__main__':
    main()


Measured memory_bytes: 9720
n,m = gets.split.map &:to_i

#つながってる島の中で最も若い番号をさす
$islands = {}

def root(x)
	while $islands[x] != nil
		x = $islands[x]
	end
	
	x
end

#いくつつながっているか
$counts = Array.new(n + 1, nil)
(n + 1).times{ |i|
	$counts[i] = 1
}

as = []
bs = []

m.times{
	a, b = gets.split.map &:to_i
	
	as << a
	bs << b
}

#初期不便度
count = n * (n - 1) / 2

result = [count]

(m-1).downto(1) { |i|
	root_a = root(as[i])
	root_b = root(bs[i])

	temp_a_count = $counts[root_a]
	temp_b_count = $counts[root_b]

	if root_a != root_b then
		master = nil
		slave = nil
	
		if root_a > root_b then
			master = root_b
			slave = root_a
		else
			master = root_a
			slave = root_b
		end

		$islands[slave] = master
		$counts[master] += $counts[slave]

		count -= temp_a_count * temp_b_count
	end

	result << count
}

puts result.reverse.join("\n")


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

int N;

int main(){
    cin >> N;
    vector<int> ai = vector<int>(N);
    int buf;
    double sum = 0;
    for(int i = 0; i<N; i++){
        cin >> buf;
        ai.at(i) =  buf;
        sum += buf;
    }

    // double dd = sum / N;
    // int db = (int)dd;
    // printf("%lf\n", dd - (double)db);
    // if(dd -(double)db >= 0.5){
    //     printf("change\n");
    //     db++;
    // }
    double dd = sum / N;
    int db = round(dd);

    int ans = 0;
    for(int xx : ai){
        // printf("%d\n", xx);
        ans += pow(xx-db, 2.0);
    }

    cout << ans << endl;



}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define allR(v) v.rbegin(), v.rend()
#define PRINT(v) for (auto x : (v)) cout <<x <<" " ; cout <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
typedef pair<int,int> Pi;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
const int inf = 1001001001;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> inline bool chmin(T& a, T b){if (a>b){a = b; return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if (a<b){a = b; return true;}return false;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }

template<class T> struct edge { int to; T cost;};


int main() {
  int N,K; cin >>N >>K;
  vector<int> V(N); rep(i, N) cin >>V[i];
  int res = 0;
  for (int i=0; i<N; i++){
    for (int j=i; j<=N; j++){
      if (N - (j-i) > K) continue;
      // まず[i, j)以外を全て取り出すとする
      vector<int> Vin;
      for (int k=0; k<N; k++){
        if (i <= k && k < j) continue;
        Vin.push_back(V[k]);
      }
      sort(allR(Vin));
      // 負の価値のやつをできるだけポイする
      int Kr = K - (N - (j-i));
      for (int k=0; k<Kr; k++){
        if (Vin.size() == 0) break;
        if (Vin[Vin.size()-1] >= 0) break;
        Vin.pop_back();
      }
      int sum = 0;
      rep(k, Vin.size()) sum += Vin[k];
      chmax(res, sum);
    }
  }
  cout <<res <<endl;
}

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

using namespace std;

#define int int64_t

signed main() {
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, x;
	cin >> n >> x;
	int b[n], L[n], R[n], d[n];
	for(int i = 0; i < n; i++) {
		cin >> b[i] >> L[i] >> R[i];
		d[i] = R[i] * (x - b[i]) + L[i] * b[i];
	}
	int p[n];
	iota(p, p + n, 0);
	sort(p, p + n, [&](int x, int y) {
		return d[x] > d[y];
	});
	int psum[n + 2];
	psum[0] = 0;
	for(int it = 1; it <= n; it++) {
		int i = p[it - 1] + 1;
		psum[it] = psum[it - 1] + R[i - 1] * (x - b[i - 1]);
	}
	int ssum[n + 2];
	ssum[n + 1] = 0;
	for(int it = n; it >= 1; it--) {
		int i = p[it - 1] + 1;
		ssum[it] = ssum[it + 1] + L[i - 1] * b[i - 1];
	}
	int l = -1, r = x * n;
	while(r - l > 1) {
		int tm = (l + r) / 2;
		int m = tm;
		int div = m / x;
		int rem = m % x;
		bool ok = false;
		for(int it = 0; it < n; it++) {
			int i = p[it];
			int sum = (rem >= b[i] ? R[i] * (rem - b[i]) : L[i] * (rem - b[i]));
			sum += (it < div ? psum[div + 1] - R[i] * (x - b[i]) : psum[div]);
			sum -= (it < div ? ssum[div + 2] : ssum[div + 1] - L[i] * b[i]);
			ok |= sum >= 0;
		}
		if(ok) {
			r = tm;
		} else {
			l = tm;
		}
	}
	cout << r << endl;
	return 0;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int K, A, B ;
    cin >> K >> A >> B ;

    int a = (A-1) / K ;
    int b = B / K ;

    if( b - a > 0 )
    {
        cout << "OK" ;
    }
    else
    {
        cout << "NG" ;
    }
    cout << endl ; 
}


Measured memory_bytes: 3600
n,m = map(int,input().split())
t = [[0]*(n+2) for i in range(n+2)]

for i in range(m):
    a,b,x = map(int,input().split())
    a -= 1
    b -= 1
    t[a][b] += 1
    t[a][b+1] -= 1
    t[a+x+1][b] -= 1
    t[a+x+1][b+x+2] += 1
    t[a+x+2][b+1] += 1
    t[a+x+2][b+x+2] -= 1
    
for i in range(n+2):
    for j in range(1,n+2):
        t[i][j] += t[i][j-1]
        
for i in range(n+2):
    for j in range(1,n+2):
        t[j][i] += t[j-1][i]
    
for i in range(1, n+2):
    for j in range(1,n+2):
        t[i][j] += t[i-1][j-1]
        
ans = 0
for i in range(n):
    for j in range(i+1):
        if t[i][j] != 0:
            ans += 1
            
print(ans)


Measured memory_bytes: 597084
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = LMIIS()
    Q = II()
    counter = Counter(A)

    tmpsum = sum(A)
    ans = deque()
    
    for i in range(Q):
        b,c = LMIIS()
        num_b = counter[b]
        counter[b] = 0
        counter[c] += num_b
        tmpsum += num_b*(c-b)
        ans.append(tmpsum)
    for a in ans:
        print(a)



    # change_from = dict()
    # change_to = dict()
    # for i in range(Q):
    #     b,c = LMIIS()
    #     #変化後にbになっているものの変化先をcに変える
    #     if not b in change_from.keys():
    #         change_from[b] = b
    #     change_to[change_from[b]] = c
    #     change_to[b] = c
    #     change_from[c] = b
    

    # for a in A:
    #     if not a in change_to.keys():
    #         print(a)
    #     else:
    #         print(change_to[a])
    
main()

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

signed main() {
	ll D, c, s; cin >> D;
	for (int h = 0; h < 26; h++) {
		cin >> c;
	}
	for (int i = 0; i < D; i++) {
		for (int h = 0; h < 26; h++) {
			cin >> s;
		}
	}
	for (int h = 0; h < D; h++) {
		cout << h % 26 + 1 << endl;
	}
	return 0;
}

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

#define N 100000
#define INF 0x3f3f3f3f

int main() {
	static int aa[N];
	int n, i, i_, x, a, b, c;

	scanf("%d", &n);
	a = i_ = -1;
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]);
		if (a < aa[i]) {
			a = aa[i];
			i_ = i;
		}
	}
	b = INF;
	c = -1;
	for (i = 0; i < n; i++)
		if (i != i_) {
			x = abs(aa[i] - (a + 1) / 2);
			if (b > x) {
				b = x;
				c = i;
			}
		}
	printf("%d %d\n", a, aa[c]);
	return 0;
}


Measured memory_bytes: 512
#include"bits/stdc++.h"
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

void Main(){
    int n, x, t; cin >> n >> x >> t;
    cout << (n+x-1)/x * t << endl;
    return;
}

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

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

using namespace std;
#define int long long
int n,f[100005][2],base=1e9+7,pa[100005],con[100005],ok[100005];
vector<int> v[100005];
void BFS()
{
    queue<int> q;
    q.push(1);
    ok[1]=1;
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<v[u].size();i++)
        {
            if(ok[v[u][i]]==0)
            {
                ok[v[u][i]]=1;
                pa[v[u][i]]=u;
                q.push(v[u][i]);
                con[u]++;
            }
        }
    }
}
int F(int i,int ok)
{
    if(f[i][ok]!=-1) return f[i][ok];
    else if(con[i]==0) return 1;
    else
    {
        //cout<<i<<" "<<ok<<'\n';
        int gt=1;
        for(int j=0;j<v[i].size();j++)
        {
            if(i==pa[v[i][j]])
            {
                int res=0;
                res=(res+F(v[i][j],0))%base;
                if(ok==0) res=(res+F(v[i][j],1))%base;
                gt=(gt*res)%base;
            }
        }
        f[i][ok]=gt;
        return gt;
    }
}
main()
{
    cin>>n;
    memset(f,-1,sizeof(f));
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    BFS();
    //cout<<con[2];
    cout<<(F(1,0)+F(1,1)+base)%base<<'\n';
    //cout<<F(1,0)<<" "<<F(1,1);
}


Measured memory_bytes: 16512
import sys
input = sys.stdin.readline

n=int(input())
dp=[[0]*10 for _ in range(10)]

for i in range(1,n+1):
    dp[int(str(i)[0])][int(str(i)[-1])]+=1

#print(dp)
ans = 0
for i in range(10):
    for j in range(10):
        ans+=dp[i][j]*dp[j][i]
print(ans)
    


Measured memory_bytes: 73576
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		long[] arr = new long[n];
		for (int i = 0; i < n; i++) {
			arr[i] = s.nextLong();
		}
		long[][] dp = new long[n][n];
		for (int i = 0; i < n; i++)
			Arrays.fill(dp[i], Long.MIN_VALUE);
		System.out.println(rec(arr, 0, n - 1, dp));
	}

	public static long rec(long[] arr, int i, int j, long[][] dp) {
		if (i == j) {
			dp[i][j] = arr[i];
			return dp[i][j];
		}
		if (dp[i][j] != Long.MIN_VALUE)
			return dp[i][j];

		dp[i][j] = Math.max(arr[i] - rec(arr, i + 1, j, dp), arr[j] - rec(arr, i, j - 1, dp));
		return dp[i][j];
	}
}


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

string a,b;
int n;

int dp[10010][3];

int f(int x,int y){
	if(x==n+1) return y;
	int bit = (a[2*x] == 'Y' || a[2*x+1] == 'Y') | ((b[2*x] == 'Y' || b[2*x+1] == 'Y')<<1);
	if(~dp[x][y]) return dp[x][y];
	if(bit == 0) return dp[x][y] = f(x+1,y);
	
	if(bit == 1 && y == 0) return dp[x][y] = min(f(x+1,1),f(x+1,0))+1;
	if(bit == 2 && y == 0) return dp[x][y] = min(f(x+1,1),f(x+1,2))+2;
	if(bit == 3 && y == 0) return dp[x][y] = min(f(x+1,1),f(x+1,2))+2;
	
	if(bit == 1 && y == 1) return dp[x][y] = min(f(x+1,1),f(x+1,0))+1;
	if(bit == 2 && y == 1) return dp[x][y] = min(f(x+1,1),f(x+1,2))+1;
	if(bit == 3 && y == 1) return dp[x][y] = min(f(x+1,1),min(f(x+1,0),f(x+1,2)))+2;

	if(bit == 1 && y == 2) return dp[x][y] = min(f(x+1,0),f(x+1,1))+2;
	if(bit == 2 && y == 2) return dp[x][y] = min(f(x+1,1),f(x+1,2))+1;
	if(bit == 3 && y == 2) return dp[x][y] = min(f(x+1,1),f(x+1,0))+2;
	
}
/*
N YN NY YN N
N YN YY NN N
*/
int main(){
	cin >> n;
	while(cin >> n){
		string s;
		cin >> s;
		a = "N" + s.substr(0,2*n) + "N";
		b = "N" + s.substr(2*n,2*n) + "N";
		memset(dp,-1,sizeof(dp));
		cout << f(0,0)+n << endl;
	}
}

Measured memory_bytes: 0
import sys
import math
input = sys.stdin.readline

def get_max(vec: list) -> int:
    reference = vec[0]
    diffs = -1 * 1e+9
    for x in vec[1:]:
        _diffs = reference - x
        if diffs < _diffs:
            diffs = _diffs
        if reference < x:
            reference = x
    return diffs

if __name__ == "__main__":
    n = int(input())
    res = 0
    vec = []
    for _ in range(n):
        vec.append(int(input()))
    print(get_max(list(reversed(vec))))



Measured memory_bytes: 16588
#include "bits/stdc++.h"

#define rep(j,n) for(int j=0;j<n;j++)
#define ll long long
#define MX 1005

#define pb .push_back

using namespace std;

int main(){
    int n,a[MX][MX];
    cin>>n;
    rep(i,n)rep(j,n-1){
        cin>>a[i][j];
        a[i][j]--;
        }
    int j[MX],ans=0;
    memset(j,0,sizeof(j));
    bool f=false,g[MX];

    while(1){
        ans++;
        f=false;
        rep(i,n)g[i]=false;
        rep(i,n){
            if(j[i]==n-1)continue;
            int b=a[i][j[i]];
            if(!g[i]&&!g[b])
            if(a[b][j[b]]==i){
                j[i]++;
                j[b]++;
                g[i]=true;
                g[b]=true;
                f=true;
            }
        }
        rep(i,n){
            if(j[i]!=n-1)break;
            if(i==n-1){
                cout<<ans<<endl;
                return 0;
            }
        }
        if(!f){
            cout<<-1<<endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 4352