akhauriyash/Code-Regression huggingface dataset:
n,m=[int(x) for x in input().rstrip().split()]
ll=[]
rl=[]
for i in range(m):
  l,r=[int(x) for x in input().rstrip().split()]
  ll.append(l)
  rl.append(r)

ans=0
if min(rl)-max(ll)<0:
  print(0)
else:
  print(min(rl)-max(ll)+1)
 

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

using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;

    if (k == 0) {
        cout << n * n << endl;
        return 0;
    }

    long long ans = 0;
    for (long long b = k + 1; b <= n; ++b) {
        ans += (n / b) * (b - k) + fmax(0, n % b - k + 1);
    }

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

Measured memory_bytes: 256
use proconio::{input, fastout};

#[fastout]
fn main() {
    input! {
        mut a: i64,
        b: i64,
        mut c: i64,
        d: i64,
    }

    while a > 0 && c > 0 {
        c -= b;
        a -= d;
    }

    if a <= 0 && c <= 0 {
        println!("Yes");
    } else if a <= 0 {
        println!("No")
    } else {
        println!("Yes")
    }
}


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

int a[1000010];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    sort(a, a+n);
    reverse(a, a+n);
    long long ans = a[0];
    multiset<int> p;
    p.insert(a[1]);
    p.insert(a[1]);
    for(int i=2;i<n;i++){
        ans += *p.rbegin();
        p.erase(--p.end());
        p.insert(a[i]);
        p.insert(a[i]);
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 13904
#include <stdio.h>
 
int main(void){

	int n, i, j,  min, max, sum;

	while( scanf("%d", &n ) != EOF ) {
		if( !n ) break;
		min = 1000;
		sum = 0;
		max = 0;
		for( i = 0; i < n; i++ ) {
			scanf("%d", &j );
			if( j < min )
				min = j;
			if( j > max )
				max = j;
			sum += j;
		}
		printf("%d\n", (sum - max - min)/(n-2) );
	}

	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
using ll=long long;using ull=unsigned ll;
using vi=vector<int>;using vvi=vector<vi>;using vl=vector<ll>;
using P=pair<int,int>;using PL=pair<ll,ll>;
const int INF=1<<30,MOD=1000000007;const ll LINF=1ll<<60;
#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##_l=(b);i<i##_l;++i)
#define REP(...) _overload3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n) for(int i=n-1;i>=0;--i)
#define REPARR(i,v) for(int i=0;i<v.size();++i)
#define all(v) (v).begin(),(v).end()
#define uniq(v) sort(all(v));v.erase(unique(all(v)),v.end())
#define bit(n) (1ll<<(n))
template<class T>bool chmax(T&a,const T&b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,const T&b){if(a>b){a=b;return 1;}return 0;}
#define cut(n, Min, Max) max(min(n,Max),Min)
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define yes(n) cout<<((n)?"yes":"no")<<endl
#define poss(n) cout<<((n)?"":"im")<<"possible"<<endl
#define Poss(n) cout<<((n)?"P":"Imp")<<"ossible"<<endl
template<typename T>ostream&operator<<(ostream&o,const vector<T>&v){for(T i:v)o<<i<<' ';return o;}
template<typename T>istream&operator>>(istream&i,vector<T>&v){for(T&j:v)i>>j;return i;}
template<typename T>ostream&operator<<(ostream&o,const set<T>&v){for(T i:v)o<<i<<' ';return o;}
template<typename T,typename U>ostream&operator<<(ostream&o,const pair<T,U>&v){o<<v.first<<' '<<v.second;return o;}

int main(){
    int n,m;
    cin>>n>>m;
    vector<int> b(m);
    REP(i,n){
        int k;
        cin>>k;
        REP(j,k){
            int a;cin>>a;
            b[a-1]++;
        }
    }
    int ans=0;
    REP(i,m){
        if(b[i]==n)ans++;
    }
    cout<<ans<<endl;
    return 0;
}


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

bool date[1000010];

bool Search(int n){
  if(date[n]){
    return true;
  }else{
    date[n] = true;
    return false;
  }
}

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

  memset(date,false,sizeof(date));
  int i = 1;
  while(!Search(s)){
    i++;
    if(s % 2 == 0){
      s /= 2;
    }else{
      s = s*3 + 1;
    }
  }
  cout << i << endl;
  return 0;
}


Measured memory_bytes: 1280
use proconio::{fastout, input};

#[fastout]
fn main() {
    input!(n: [usize; 5]);

    let mut min = 10;

    let mut sum = 0;
    for v in &n {
        let d_v = *v % 10;

        if d_v != 0 {
            min = std::cmp::min(min, d_v);
        }

        sum += *v + (10 - d_v) % 10;
    }
    println!("{}", sum - (10 - min) % 10);
}


Measured memory_bytes: 2176
#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 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 T, class U>bool chmax(T& a, U&& b) { return a < b ? a = b, 1 : 0; }
template<class T, class U>bool chmin(T& a, U&& 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() {
    const vector<string> date = { "SUN","MON","TUE","WED","THU","FRI","SAT" };
    string S;
    cin >> S;

    rep(i, 7) if (date[i] == S) {
        int ans = 7 - i;
        write(ans);
        return 0;
    }
}

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

int main(){
	double a, b, rad;
	cin >> a >> b >> rad;
	rad = rad/180*M_PI;
	cout << fixed << setprecision(5) << a*sin(rad)*b/2 << '\n'
	<< a+b+sqrt(pow(a, 2)+pow(b, 2)-2*a*b*cos(rad)) << '\n'
	<< b*sin(rad) << endl;
	return 0;
}


Measured memory_bytes: 3528
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int INF = (int)1e9 + 7;

int main() {
    int n; cin >> n;
    string s; cin >> s;
    vector<int> accE(n + 1);
    for (int i = 0; i < n; i++) accE[i + 1] = accE[i] + (s[i] == 'E');
    int mi = INF;
    for (int i = 0; i < n; i++) {
        int leftW = i - accE[i], rightE = accE[n] - accE[i + 1];
        mi = min(mi, leftW + rightE);
    }
    cout << mi << endl;
    return 0;
}


Measured memory_bytes: 1796
#include <bits/stdc++.h>
#define rep(i,a,n)  for (int i=(int)(a); i<=(int)(n); ++i)
#define rrep(i,a,n) for (int i=(int)(a); i>=(int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) rep(i, x.size()) cerr << x[i] << (i == x.size() - 1 ? "\n" : " ")
#define all(x) x.begin(),x.end()
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = ((1LL << 30) + (1LL << 29));
const int MOD = 1000000007;

//=============================
int N,M,K;
string S,T;
vector<int> A;
vector<int> B;
//=============================
void input()
{
    cin>>S;

}
//=============================
void func(){}
//=============================
void solve()
{
    set<char> st;
    rep(i,0,S.size()-1) {
        st.insert(S[i]);
    }
    bool ans = (st.size()==3);
    cout<<(ans? "Yes" : "No")<<endl;

}
//=============================
signed main()
{
    input();
    solve();
    return 0;
}

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

int main() {
  int K, A, B;
  cin >> K >> A >> B;
  while (true) {
    if (B % K == 0) {
      cout << "OK" << endl;
      break;
    }
    else if (B == A) {
      cout << "NG" << endl;
      break;
    }
    B--;
  }
}

Measured memory_bytes: 3672
# 169A
# A × B を整数として出力せよ

# 1.入力をプログラムで扱えるように受け取ること
a, b = map(int, input().split())

# 2.受け取った入力値を使って、適切に処理（計算）すること
answer = a * b

# 3.計算した結果を出力すること
print(answer)


Measured memory_bytes: 9112
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

a,b=l_in()

for x in range(1001):
    if x*8//100 == a and x*10//100 == b:
        print(x)
        break
else:
    print(-1)



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

using namespace std;

using int64 = long long;

constexpr int64 P = 1000000007;

// Verified: ABC133E, ABC132D, ABC130E
struct FiniteField {
 private:
  int64 x;
 public:
  FiniteField(int64 input_x) : x(input_x) {}
  FiniteField() : x(0) {}
  int64 Value() { return x; }
  inline FiniteField operator+(FiniteField o) {
    FiniteField r(*this); r += o; return r;
  }
  inline FiniteField operator-(FiniteField o) {
    FiniteField r(*this); r -= o; return r;
  }
  inline FiniteField operator* (FiniteField o) {
    FiniteField r(*this); r *= o; return r;
  }
  inline FiniteField operator/ (FiniteField o) {
    FiniteField r(*this); r /= o; return r;
  }
  inline void operator+= (FiniteField o) { x = (x + o.x) % P; }
  inline void operator-= (FiniteField o) { x = (x + P - o.x) % P; }
  inline void operator*= (FiniteField o) { x = (x * o.x) % P; }
  void operator/=(FiniteField o) {
    int64 p = P - 2; while (p) { if (p % 2) { *this *= o; } o *= o; p /= 2; }
  }
};

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

  int n;
  string s;
  cin >> n >> s;

  vector<vector<FiniteField>> dp1(n);
  vector<vector<FiniteField>> dp2(n);
  dp1[0] = vector<FiniteField>(n);
  for (int j = 0; j < n; j++) {
    dp1[0][j] = 1;
  }
  dp2[0] = vector<FiniteField>(n);
  dp2[0][0] = dp1[0][0];
  for (int j = 1; j < n; j++) {
    dp2[0][j] = dp2[0][j - 1] + dp1[0][j];
  }

  for (int i = 0; i < n - 1; i++) {
    dp1[i + 1] = vector<FiniteField>(n);
    dp2[i + 1] = vector<FiniteField>(n);

    for (int j = 0; j < n - i; j++) {
      if (s[i] == '<') {
        dp1[i + 1][j] = dp2[i][j];
      } else {
        // s[i] == '>'
        dp1[i + 1][j] = dp2[i][n - i - 1] - dp2[i][j];
      }
    }

    dp2[i + 1][0] = dp1[i + 1][0];
    for (int j = 1; j < n - (i + 1); j++) {
      dp2[i + 1][j] = dp2[i + 1][j - 1] + dp1[i + 1][j];
    }

    // cout << "i: " << i + 1 << endl;
    // for (int j = 0; j < n - (i + 1); j++) {
    //   cout << dp1[i + 1][j].Value() << " ";
    // }
    // cout << endl;
    // for (int j = 0; j < n - (i + 1); j++) {
    //   cout << dp2[i + 1][j].Value() << " ";
    // }
    // cout << endl;
  }

  cout << dp1[n - 1][0].Value() << endl;
}


Measured memory_bytes: 141184
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}
 
ll memo[2][1005][1005] = {0};
char c;
ll x,y,bw,n,k;
 
ll solve(){
  ll ans = 1, now[2];
  rep(i,k)rep(j,k)rep(l,2){
    now[l] = memo[l][i][j];
    if(i != k-1 && j != k-1){
      now[l] += memo[l][k-1][k-1];
      now[l] -= memo[l][i][k-1];
      now[l] -= memo[l][k-1][j];
      now[l] += memo[l][i][j];
    }
    now[l] += memo[1-l][k-1][j] - memo[1-l][i][j];
    now[l] += memo[1-l][i][k-1] - memo[1-l][i][j];
    ans = max(ans, now[l]);
  }
  return ans;
}
 
int main(){
  cin >> n >> k;
  for(int i = 0; i < n; i++){
    cin >> x >> y >> c;
    bw = (c == 'B');
    memo[(x/k + y/k + bw)%2][x%k][y%k]++;
  }
  
  rep(l,2)rep(i,k)rep(j,k){
    if(j != 0) memo[l][i][j] += memo[l][i][j-1];
    if(i != 0) memo[l][i][j] += memo[l][i-1][j];
    if(i != 0 && j != 0){
      memo[l][i][j] -= memo[l][i-1][j-1];
    }
  }
  
  cout << solve() << endl;
 
  return 0;
}

Measured memory_bytes: 16000
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define ii pair<ll,ll>
#define vii vector<ii>
#define F first
#define S second
#define INF -1000000000

using namespace std;

int h,w;
vector<string> maze;
ll dp[1004][1004];
bool est[1004][1004];
ll solve(int i,int j){
//	cout << i << " " << j << endl;
	if(i < 0 || i == h || j < 0 || j == w) return 0;
	if(dp[i][j] != -1) return dp[i][j];
	if(i == h-1 && j == w-1) return 1;
	if(est[i][j] || maze[i][j] == '#') return 0;
	est[i][j] = 1;
	dp[i][j] = solve(i+1,j)+solve(i,j+1);
	dp[i][j] %= (1000000007);
	return dp[i][j];
}


int main(){
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> h >> w;
	string temp;
	for (int i = 0; i < h; ++i){
		cin >> temp;
		maze.push_back(temp);
	}
	for (int i = 0; i < 1004; ++i){
		for (int j = 0; j < 1004; ++j){
			dp[i][j] = -1;
			est[i][j] = 0;
		}
	}

	cout << solve(0,0) << endl;

	return 0;
}

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

#define fast ios_base:: sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pb emplace_back
#define mp make_pair
#define ff first
#define ss second

typedef long long ll;
typedef long double ld;
int main(){
	fast;
	int a[3];
	cin >> a[0] >> a[1] >> a[2];
	
	int ans = 303;
	for(int i=0 ; i<3 ; i++){
		ans = min(ans,a[i%3] + a[(i+1)%3]);
	}
	cout << ans;
}






Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <deque>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

// author:Swastik Banerjee

using namespace std;

typedef long long ll;
#define MOD 1000000007

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



  ll a, n;
  cin >> a >> n;
  ll arr[n];
  ll sum = 0;
  for (ll i = 0; i < n; i++) {
    cin >> arr[i];
    sum += arr[i];
  }

  //cout << sum << endl;

  if (sum >= a)
    cout << "Yes\n";
  else
    cout << "No\n";
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;



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

int a, b;
  cin>>a>>b;
  
  int k = (a+b)/2;
  
  if(abs(a-k)==abs(b-k)) cout<<k<<endl;
  else cout<<"IMPOSSIBLE"<<endl;

  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
const int INF = 1000000007;
typedef long long ll;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int main(){
  // ios::sync_with_stdio(false);cin.tie(nullptr);
  ll n;
  cin >> n;
  ll ans = 0;
  REP(b,1,100){
    REP(p,2,100){
      if(pow(b,p) <= n)ans = max(ans,(ll)pow(b,p));
    }
  }
  cout << ans << endl;
  return 0;
}

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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define MP make_pair
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
ll INF = 1e18;
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x,ll y,ll z){if(x)cout<<y<<endl;else cout<<z<<endl;}
void ans(bool x,string y,string z){if(x)cout<<y<<endl;else cout<<z<<endl;}   
ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;}

int main(){
  ll i,j,o;
  ll res=0,res1=INF,res2=-INF,buf=0,buf1=0,buf2=0,buf3=0,buf4=0,sum=0;
  ll l,r;
  bool judge = true;
  ll n,m;cin>>n>>m;
  ll MAX_V=n+1;
  vector<vector<ll>> matrix(MAX_V,vector<ll>(MAX_V,INF));
  for(i=0;i<MAX_V;i++)matrix[i][i]=0;
  vector<ll>a(m),b(m),c(m);
  for(i=0;i<m;i++){
    cin>>a[i]>>b[i]>>c[i];
    matrix[a[i]][b[i]]=c[i];
    matrix[b[i]][a[i]]=c[i];
  }
  for(j=0;j<MAX_V;j++){
    for(i=0;i<MAX_V;i++){
      for(o=0;o<MAX_V;o++){
        chmin(matrix[i][o],matrix[i][j]+matrix[j][o]);
      }
    }
  }

  for(i=0;i<m;i++){
    if(matrix[a[i]][b[i]]<c[i])res++;
  }
  cout<<res<<endl;
  
  return 0;
}

Measured memory_bytes: 384
#coding:utf-8
s=raw_input()

win=lose=0
b=0
for c in s:
    t=""
    if b==0:
        t="g"
        b+=1
    else:
        t="p"
        b-=1
    if c=="g" and t=="p":win+=1
    if c=="p" and t=="g":lose+=1
print(win-lose)

Measured memory_bytes: 32668
def main():
    N, A = map(int, input().split())
    X = tuple(map(int, input().split()))

    x = [i - A for i in X]
    nx = max(X) * N
    dp = [[0] * (2 * nx + 1) for _ in [0] * (N + 1)]
    for i in range(N + 1):
        for j in range(2 * nx + 1):
            if not i:
                if j == nx:
                    dp[i][j] = 1
            elif j - x[i-1] < 0 or j - x[i-1] > 2 * nx:
                dp[i][j] = dp[i-1][j]
            elif 0 <= j - x[i-1] <= 2 * nx:
                dp[i][j] = dp[i-1][j] + dp[i-1][j - x[i-1]]
    print(dp[N][nx] - 1)

main()


Measured memory_bytes: 5604
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}
const int dm = 1 << 20;
char dn[dm], * di = dn;
inline void putint(ll X) {
	if (!X) {
		*di++ = '0';
		*di++ = '\n';
		return;
	}
	int keta = 0;
	char C[20];
	while (X) {
		*(C + keta) = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--)* di++ = (*(C + i));
	*di++ = '\n';
}
void pakuri_sort(int N, int A[]) {
	const int b = 8;
	int tmp[100001];
	rep(k, 4) {
		int kazu[1 << b] = {}, kazu2[1 << b] = {};
		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];
		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];
		k++;
		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];
		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];
	}
}
int A[100000];
int C[100001];
int MA[100001], MI[100001];
int saidai, k = 1;
ll kotae[100001];

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


	int N = getint();
	int k3 = 0;
	rep(i, N) {
		int a = getint();
		if (a > saidai) {
			MA[k] = a;
			MI[k] = i;
			kotae[i] += a - saidai;
			C[k++]++;
			saidai = a;
		}
		else A[k3++] = a;
	}
	pakuri_sort(k3, A);
	int k2 = 1;
	rep(i, k3) {
		while (MA[k2] < A[i]) k2++;
		kotae[MI[k2]] += A[i] - MA[k2 - 1];
		C[k2]++;
	}

	ll cnt = 0;
	for (int i = k - 1; i >= 1; i--) {
		kotae[MI[i]] += (MA[i] - MA[i - 1]) * cnt;
		cnt += C[i];
	}

	rep(i, N) putint(kotae[i]);

	fwrite_unlocked(dn, di - dn, 1, stdout);

	Would you please return 0;
}

Measured memory_bytes: 3968
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

void solve() {
    int N;
    cin >> N;
    vi A(N);
    rep(i, N)cin >> A[i];
    ll sum = 0;
    rep(i, N) {
        if (i & 1)sum -= A[i];
        else sum += A[i];
    }
    
    vll ans(N);
    ans[0] = sum / 2;
    FOR(i, 1, N - 1) {
        ans[i] = A[i - 1] - ans[i - 1];
    }
    ans[N - 1] = A[N - 1] - ans[0];
    rep(i, N)cout << ans[i]*2ll << (i != N - 1 ? ' ' : '\n');
}

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


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

int main(){
  int W,H,N;
  cin >> W >> H >> N;
  vector<vector<int>> B(H,vector<int>(W,0));
  vector<int> X(N),Y(N),A(N);
  for(int i=0;i<N;i++){
    cin >> X.at(i) >> Y.at(i) >> A.at(i);
  }
  for(int i=0;i<N;i++){
    if(A.at(i)==1){
      for(int j=0;j<H;j++){
        for(int k=0;k<X.at(i);k++){
          B.at(j).at(k)++;
        }
      }
    }
    else if(A.at(i)==2){
       for(int j=0;j<H;j++){
        for(int k=X.at(i);k<W;k++){
          B.at(j).at(k)++;
        }
       }
    }
    else if(A.at(i)==3){
       for(int j=0;j<Y.at(i);j++){
        for(int k=0;k<W;k++){
          B.at(j).at(k)++;
        }
       }
    }
    else if(A.at(i)==4){
       for(int j=Y.at(i);j<H;j++){
        for(int k=0;k<W;k++){
          B.at(j).at(k)++;
        }
       }
    }
  }
  int count=0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(B.at(i).at(j)==0){
        count++;
      }
    }
  }
  cout << count << endl;
}     

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
	char S[5];
	int i;
	scanf("%s",&S);
	for(i=0;i<4;i++){
		if(S[i]=='A'&&S[i+1]=='C'){
			printf("Yes\n");
			return 0;
		}
	}
	printf("No\n");
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
using vint = std::vector<int>;
using wint = std::vector<vint>;

int main(void){
    std::vector<wint> D(4, wint(3, vint(10, 0)));
    int n; scanf("%d", &n);
    while(n--){
        int b, f, r, v; scanf("%d%d%d%d", &b, &f, &r, &v);
        D[b-1][f-1][r-1]+=v;
    }
    for(int i = 0; i < 4; ++i){
        for(int j = 0; j < 3; j++){
            for(int k = 0; k < 10; k++){
                putchar(' ');
                putchar('0' + D[i][j][k]);
            }
            putchar('\n');
        }
        if(i != 3){for(int k = 0; k < 20; k++) putchar('#'); putchar('\n');}
    }
    return 0;
}


Measured memory_bytes: 3176
#prag\
ma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#define ll long long
int main()
{
	ios::sync_with_stdio(false);
	int n,k;
	cin>>n>>k;
	ll ans=0;
	for(int i=1;i<=n;++i){
		int x=i-k;
		if(x<0) continue;
		ans+=(ll)(n/i)*(ll)x;
		if(n%i!=0&&n%i>=k) ans+=(ll)((n%i)-max(k,1)+1);
	}
	cout<<ans;
}

Measured memory_bytes: 256
import java.util.*;

class Main {
        public static void main(String args[]) {
                Scanner sc = new Scanner(System.in);
                int x[] = new int[31];
                for (int i = 0; i < 28; i++) {
                        x[sc.nextInt()] = 1;
                }
                for (int i = 1; i <= 30; i++) {
                        if (x[i] != 1) {
                                System.out.println(i);
                        }
                }
        }
}

Measured memory_bytes: 26008
////////////////////////////////////
///     Please Give Me AC!!!     ///
////////////////////////////////////

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define forin(in) for(int i=0; i<(int)in.size(); i++) cin>>in[i]
#define forout(out) for(int i=0; i<(int)out.size(); i++) cout<<out[i]<<endl
#define rep(i, n) for(int i=0; i<(n); i++)

int main(){
    string s;
    cin>> s;
    int N = s.size();
    string ans;

    rep(i, N){
        if(s[i] == '0'){
            ans.push_back('0');
        }else if(s[i] == '1'){
            ans.push_back('1');
        }else{
            if(!ans.empty()){
                ans.pop_back();
            }
        }
    }
    cout<< ans << endl;
}

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

bitset<26> INF;

vector<bitset<26>> value; // ノードの値を持つ配列
int N;             // 葉の数

void update(int i, int x, int y) {
  // i 番目の葉の値を x から yに変える
  i += N - 1; // i 番目の葉のノード番号
  value[i].set(x,0);
  value[i].set(y,1);
  while (i > 0) {
    i = (i - 1) / 2; // ノード i の親ノードの番号に変える
    value[i] = value[i * 2 + 1]|value[i * 2 + 2];
  }
}

bitset<26> query(int a, int b, int k, int l, int r) {
  // [a, b) の区間に対するクエリについて
  // ノード k （区間 [l, r) 担当）が答える
  if (r <= a || b <= l) return INF; // 区間が被らない場合は INF を返す
  if (a <= l && r <= b)
    return value[k]; // ノード k の担当範囲がクエリ区間 [a, b)
  // に完全に含まれる
  else {
    bitset<26> c1 = query(a, b, 2 * k + 1, l, (l + r) / 2); // 左の子に値を聞く
    bitset<26> c2 = query(a, b, 2 * k + 2, (l + r) / 2, r); // 右の子に値を聞く
    return c1|c2; // 左右の子の値の min を取る
  }
}

int main(){
  int n;
  cin >> n;
  string S;
  cin >> S;
  
  N = 1;
  while (N < n) N *= 2; // 葉の数を計算（n以上の最小の2冪数)
  value = vector<bitset<26>>(2*N-1);
  
  for(int i=0; i<S.size(); i++){
    int x = S.at(i) - 'a';
    update(i,x,x);
  }
  int Q;
  cin >> Q;
  for(int i=0; i<Q; i++){
    int a;
    cin >> a;
    if(a == 1){
      int b;
      cin >> b;
      char c;
      cin >> c;
      b--;
      int x = S.at(b) - 'a';
      int y = c - 'a';
      S.at(b) = c;      
      update(b,x,y);
    }
    else{
      int b, c;
      cin >> b >> c;
      b--; c--;
      bitset<26> ans = query(b,c+1,0,0,N);
      int cnt = 0;
      for(int j=0; j<26; j++){
        if(ans.test(j)){
          cnt++;
        }
      }
      cout << cnt << endl;
    }
  }
} 

Measured memory_bytes: 9092
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007
signed main()
{
    SPEED;
    int n,m;
    cin>>n>>m;
    cout<<(n*(n-1))/2+(m*(m-1))/2;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        int a = stdIn.nextInt();

        if(a == 7){
            System.out.println("Yes");
            return;
        }

        while(a/10 >0){
            if(a%10 == 7){
                System.out.println("Yes");
                return;
            }
            a/= 10 ;
            if(a%10 == 7){
                System.out.println("Yes");
                return;
            }
        }
        System.out.println("No");
    }
}

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

int main(){
     ll n,i,s=0;
     string st;
     cin>>st;
     if(st[0]==st[1]&&st[1]==st[2] ||st[1]==st[2]&&st[1]==st[3] )
     cout<<"Yes";
     else cout<<"No";
}




Measured memory_bytes: 256
def main():
    N, M = map(int, input().split())
    shop_drink = [[int(i) for i in input().split()] for n in range(N)]
    # ドリンクの金額でソートする
    # sorted(shop_drink)
    shop_drink.sort()
    buy_drinks = 0
    buy_amount = 0

    for sd in shop_drink:
        # 購入可能数と購入済数の和が，目標数に満たない場合
        if buy_drinks + sd[1] < M:
            # 購入済数を増やす
            buy_drinks += sd[1]
            # 合計金額に加算する
            buy_amount += sd[0] * sd[1]
        # 購入可能数と購入済み数の和が，目標数以上となる場合
        else:
            # 必要数を計算
            temp = M - buy_drinks
            buy_amount += sd[0] * temp
            print(buy_amount)
            return


if __name__ == '__main__':
    main()


Measured memory_bytes: 21608
k = int(input())
from collections import deque

d = deque()
c = 0
for i in range(1, 10):
  d.append(i)

while True:
  tmp = d.popleft()
  c += 1
  if c == k:
    ans = tmp
    break
  if tmp % 10 != 0:
    d.append(tmp * 10 + (tmp % 10 - 1))
  d.append(tmp * 10 + tmp % 10)
  if tmp % 10 != 9:
    d.append(tmp * 10 + (tmp % 10 + 1))
print(ans)


Measured memory_bytes: 74840
const main = (input) => {
  const [A, B, C, K] = input.trim().split(' ').map(v => parseInt(v))
  if (A >= K) return console.log(K)
  if (A + B >= K) return console.log(A)
  return console.log(A - (K - (A+B)))
}

process.env.MYTEST ? test() : main(require('fs').readFileSync('/dev/stdin', 'utf8'))


Measured memory_bytes: 29884
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
int gcd(int a,int b){
    if(a<b){
        int temp=a;
        a=b;
        b=temp;
    }
    int r=a%b;
    while(r){
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}

signed main(){
    int a,b;
    cin>>a>>b;
    int gcdn=gcd(a,b);
    cout<<a*b/gcdn<<endl;
    return 0;
}

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

dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
           continue

        num = 0
        for k in range(8):
            ni = i + dx[k]
            nj = j + dy[k]

            if ni < 0 or h <= ni: continue
            if nj < 0 or w <= nj: continue
            if s[ni][nj] == '#': num += 1
        
        s[i][j] = str(num)
    
for i in range(h):
    print(''.join(s[i]))

Measured memory_bytes: 3188
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <deque>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <iomanip>
#include <cstring>
#include <climits>
#include <cstdio>

#define nl '\n'

using namespace std;

long long n, a, b, x, r;

int main(){

    cin >> n >> a >> b;

    x = n/(a+b);
    r = n%(a+b);

    cout << (x*a + min(r, a));


}
 
//g++ -std=c++14 comp.cpp -o c && c.exe
//g++ -std=c++14 comp.cpp -o c; ./c.exe
//g++ -std=c++14 comp.cpp && ./a.out


//Surely this is going to AC

Measured memory_bytes: 256
import numpy as np

N, M= list(map(int, raw_input().split()))
student = [list(map(int, raw_input().split())) for i in range(N)]
checkpoint = [list(map(int, raw_input().split())) for i in range(M)]

student = np.array(student)
checkpoint = np.array(checkpoint)

for i in range(N):
    print(np.abs(checkpoint - student[i]).sum(axis=1).argmin()+1)




Measured memory_bytes: 20192
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w)
#define dump(...)
const signed INF_=1001001001; const ll INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct{template<class T> operator T(){T x;cin>>x;return x;}} IN;
struct before_main_function {
    before_main_function() {
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N;
    cin>>N;
    vector<int> a(N);
    cin>>a;
    bitset<4000010> dp[2];
    dp[0]=1;
    REP(i,N) {
        dp[(i+1)%2]|=dp[i%2];
        dp[(i+1)%2]|=dp[i%2]<<a[i];
        dp[i%2]=0;
    }
    int sum=accumulate(ALL(a),0ll);
    REPF(i,sum/2,4000010) {
        if(i*2>=sum && dp[N%2][i]) {
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}


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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define forn(i, a, n) for (int i = a; i < n; ++i)
#define ford(i, a, n) for (int i = n - 1; i >= a; --i)
#define fore(i, a, n) for (int i = a; i <= n; ++i)
#define all(a) (a).begin(), (a).end()
#define fs first
#define sn second
#define trace(a)\
	for (auto i : a) cerr << i << ' ';\
	cerr << '\n'
#define eb emplace_back

#ifndef M_PI
const ld M_PI = acos(-1.0);
#endif

const ld eps = 1e-9;
const int INF = 2000000000;
const ll LINF = 1ll * INF * INF;
const ll MOD = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
    string s;
    cin >> s;
    int n = s.length();
    ll ans = 0;
    forn(m, 0, (1 << (n - 1))) {
        ll sm = 0, cur = s[0] - '0';
        forn(j, 1, n) {
            if (m & (1 << (j - 1))) {
                sm += cur;
                cur = s[j] - '0';
            } else cur = 10 * cur + (s[j] - '0');
        }
        sm += cur;
        ans += sm;
    }
    cout << ans << '\n';
}


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

using namespace std;

int RGB(char c) {
	if (c == 'R') return 0;
	if (c == 'G') return 1;
	return 2;
}

int main() {
	int n; cin >> n;
	string s; cin >> s;
	vector<vector<int> > cnt(n, vector<int>(3));
	++cnt[0][RGB(s[0])];
	for (int i = 1; i < n; ++i) {
		++cnt[i][RGB(s[i])];
		for (int j = 0; j < 3; ++j) cnt[i][j] += cnt[i - 1][j];
	}
	long long ans = 0;
	for (int i = 0; i < n - 2; ++i) {
		for (int j = i + 1; j < n - 1; ++j) {
			if (s[i] == s[j]) continue;
			int kcolor = 0;
			if (RGB(s[i]) * RGB(s[j]) == 0) {
				if (RGB(s[i]) == 1 || RGB(s[j]) == 1) kcolor = 2;
				else kcolor = 1;
			}
			ans += cnt[n - 1][kcolor] - cnt[j][kcolor];
			if (j + j - i < n && RGB(s[j + j - i]) == kcolor) --ans;
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3856
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <map>
#include <queue>
#include <array>
#include <bitset>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<pii> vii;
typedef vector<string> vs;
const int mod = 1000000007;

ll mpow(ll x, ll n) {
  ll r = 1;
  while (n) {
    if (n &1) r = r*x%mod;
    x=x*x%mod;
    n /= 2;
  }
  return r;
}

vl fac(300000, 1);
vl invfac(fac.size(), 1);

ll bin(int k, int n) {
  if (k < 0 || k > n) return 0;
  return fac[n] * invfac[k] % mod * invfac[n-k] % mod;
}

int main() {
  for (int  i = 2; i < fac.size(); ++i) {
    fac[i] = fac[i-1] * i % mod;
  }
  invfac.back() = mpow(fac.back(), mod-2);
  for (int i = fac.size() - 2; i > 0; --i) {
    invfac[i] = invfac[i+1] * (i + 1) % mod;
  }
  int h,w,a,b;
  cin >> h >> w >> a >> b;
  ll res = bin(h-1, h+w-2);
  for (int i = 0; i < b; ++i) {
    res = (res - bin(i, i + h-a-1) * bin(w-i-1, w-i-1+a-1)) % mod;
  }
  cout << (res + mod) % mod << endl;
  return 0;
}

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

namespace Practice
{
    class Program
    {
        static void Main(string[] args)
        {
            string szLine = Console.ReadLine();
            int n = int.Parse(szLine);

            int[,] data = new int[2, n];
            for (int i = 0; i < 2; ++i)
            {
                szLine = Console.ReadLine();
                string[] szArr = szLine.Split(' ');
                for (int j = 0; j < szArr.Length; ++j)
                {
                    data[i, j] = int.Parse(szArr[j]);
                }
            }

            int[] candyArrTop = new int[n];// idx ここで降りる 0~iの部分和
            candyArrTop[0] = data[0, 0];
            for(int i=1;i<n;++i)
            {
                candyArrTop[i] = candyArrTop[i - 1] + data[0, i];
            }
            int[] candyArrBtm = new int[n];// idx ここで降りる i~nの部分和
            candyArrBtm[n - 1] = data[1, n - 1];
            for( int i=n-2;i>=0;i--)
            {
                candyArrBtm[i] = candyArrBtm[i + 1] + data[1, i];
            }

            // 指定iで下に降りるぞ
            int[] candyArrTotal = new int[n];
            for(int i=0;i<n;++i)
            {
                candyArrTotal[i] = candyArrTop[i] + candyArrBtm[i];
            }

            int max = candyArrTotal.Max();
            Console.WriteLine(max);
        }
    }
}


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

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

using namespace std;

int main() {
  int N, K, C;
  cin >> N >> K >> C;
  string S;
  cin >> S;

  vector<int> earliest;
  int d = 0;
  REP(i, K) {
    while (S[d] == 'x') ++d;
    // cout << i << " " << d << endl;
    earliest.push_back(d);
    d += C + 1;
  }

  vector<int> latest;
  d = N - 1;
  REP(i, K) {
    while (S[d] == 'x') --d;
    // cout << i << " " << d << endl;
    latest.push_back(d);
    d -= C + 1;
  }

  REP(i, K) if (earliest[i] == latest[latest.size() - 1 - i]) {
    cout << earliest[i] + 1 << endl;
  }
}


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

class team{
public:
  int win, lose;
  char name;
  bool operator < (const team &s)const{
    if(win==s.win){
      return lose<s.lose;
    }
    else return win>s.win;
  }
};

main(){
  int n;
  team data[10];
  while(1){
    cin >> n;
    if(n==0) break;
    for(int i=0;i<n;i++){
      int c1=0, c2=0, tmp;
      cin >> data[i].name;
      for(int j=0;j<n-1;j++){
	cin >> tmp;
	if(tmp==0) c1++;
	else if(tmp==1) c2++;
      }
      data[i].win=c1;
      data[i].lose=c2;
    }

    stable_sort(data, data+n);

    for(int i=0;i<n;i++){
      cout << data[i].name << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 0
import sys
input=sys.stdin.readline
n=int(input())
s=input().rstrip()
l=[[] for i in range(10)]
for i in range(n):
    l[int(s[i])].append(i)
import bisect
ans=0
for x in range(10):
    if l[x]==[]:
        continue
    else:
        a=l[x][0]
        for y in range(10):
            b=bisect.bisect(l[y],a)
            if b==len(l[y]):
                continue
            else:
                b=l[y][b]
                for z in range(10):
                    c=bisect.bisect(l[z],b)
                    if c==len(l[z]):
                        continue
                    else:
                        ans+=1
print(ans)


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

typedef long long int int64;
static const int64 mod = 1000000007LL;
int64 dp[3003][3003];
int64 temp[2][3003];
int a[3003];
int n,q;
int main()
{
	scanf("%d%d",&n,&q);
	for(int i = 0;i < n;++i) {
		scanf("%d",&a[i]);
	}
	for(int i = 0;i < n;++i) {
		for(int j = 0;j < n;++j) {
			dp[i][j] = a[i] > a[j] ? 1 : 0;
		}
	}
	int64 inv2 = mod - mod / 2;
	int64 val = 1;
	for(int i = 0;i < q;++i) {
		int x,y;
		scanf("%d%d",&x,&y);--x,--y;
		for(int j = 0;j < n;++j) {
			// dp[x][j] = dp[y][j] = (dp[x][j]+dp[y][j])/2
			// swap(dp[x][y], dp[y][x])
			// dp[x][y] = dp[y][x] = (dp[x][y]+dp[y][x])/2
			temp[0][j] = (dp[x][j] + dp[y][j]) * inv2 % mod;
			temp[1][j] = (dp[j][x] + dp[j][y]) * inv2 % mod;
		}
		for(int j = 0;j < n;++j) {
			if(j != x && j != y) {
				dp[x][j] = temp[0][j];
				dp[j][x] = temp[1][j];
				dp[y][j] = temp[0][j];
				dp[j][y] = temp[1][j];
			}
		}
		int64 t2 = (dp[x][y] + dp[y][x]) * inv2 % mod;
		dp[x][y] = dp[y][x] = t2;
		val = val * 2 % mod;
	}
	int64 ans = 0;
	for(int i = 0;i < n;++i) {
		for(int j = i+1;j < n;++j) {
			ans = (ans + dp[i][j]) % mod;
		}
	}
	ans = ans * val % mod;
	printf("%lld\n", ans);
}


Measured memory_bytes: 70656
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n = ii()
A = [0]+iil()+[0]

cst = 0
for i in range(1,n+2):
    cst += abs(A[i]-A[i-1])

for i in range(1,n+1):
    minus = abs(A[i]-A[i-1])+abs(A[i+1]-A[i])
    plus = abs(A[i+1]-A[i-1])
    print(cst+plus-minus)

Measured memory_bytes: 14176
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import static java.lang.Integer.MAX_VALUE;
import static java.lang.Integer.parseInt;

/**
 * Problem 05: Split Up!
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String[] words;

		while ((line = br.readLine()) != null && !line.isEmpty()) {

			int n = parseInt(line);
			if (n == 0) break;

			int[] a = new int[n];

			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++) {
				a[i] = parseInt(st.nextToken());
			}

			int min = MAX_VALUE;

			for (int i = 0; i < 1 << n; i++) {
				int A = 0, B = 0;
				for (int j = 0; j < n; j++) {
					if ((i >> j & 1) == 1) {A += a[j];} else {B += a[j];}
				}
				min = Math.min(min, Math.abs(A - B));
			}

			System.out.println(min);
		}
	}
}

Measured memory_bytes: 25896
#include<cstdio>
#include<cstring>
#define NIL -1
#define M 1046527

// 文字から数値に変換
int getChar(char ch){
    if(ch == 'A') return 1;
    else if(ch=='C') return 2;
    else if(ch=='G') return 3;
    else if(ch=='T') return 4;
    else return 0;
}
// 文字列から数値へ変換してkeyを生成する
long long getKey(char str[]){
    long long sum=0, p=1;
    for(long long i=0; i< strlen(str);i++){
        sum += p*(getChar(str[i]));
        p*=5;
    }
    return sum;
}


int h1(int key, int m){
    return key%m;
}
int h2(int key, int m){
    return 1+(key%(m-1));
}
int find(char str[], char H[][14]){
    long long key = getKey(str);
    for(long long i=0;;i++){
        long long h = (h1(key, M) + i*h2(key, M)) % M;
        if(strcmp(H[h], str)==0) return 1;
        else if(strlen(H[h])==0) return 0;
    }
    return 0;
}
int insert(char str[], char H[][14]){
    long long key = getKey(str);
    for(long long i =0;; i++){
        long long h = (h1(key, M) + i*h2(key, M)) % M;
        if(strcmp(H[h], str)==0) return 1;
        else if(strlen(H[h])==0){
            strcpy(H[h], str);
            return 0;
        }
    }
    return 0;
}

int main(){
    int n;
    char str[14], com[9];
    char H[M][14];

    for(int i=0;  i<M;i++)H[i][0] = '\0';
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%s %s", com, str);
        if(com[0] == 'i'){
            insert(str, H);
        }
        else{
            if(find(str, H)) printf("yes\n");
            else printf("no\n");
        }
    }

    return 0;
}


Measured memory_bytes: 16936
# coding: UTF-8

CONTEST_NUM = 26

class Optimizer:

    def __init__(self, days, s, c):
        self._days = days
        self._s = s
        self._c = c

    def optimize(self):
        # 貪欲法による手法
        t = []
        for d in range(self._days):
            max_value = 0
            max_contest = 0
            for i in range(CONTEST_NUM):
                v = self._s[d][i] + self._c[i]
                if v > max_value:
                    max_value = v
                    max_contest = i
            t.append(max_contest + 1)
        return t


def main():
    ## 引数読み込み
    days = int(input()) # D
    c = tuple(map(int, input().split())) # c[i]
    s = [] # s[d][i]
    for i in range(days):
        s.append(tuple(map(int, input().split())))

    ## 試しに指標計算
    t = Optimizer(days, s, c).optimize()

    ## print out 
    for v in t:
        print(v)

if __name__ == "__main__":
    main()


Measured memory_bytes: 9316
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<list>
#include<deque>
#include<cmath>
#include<unordered_map>
#include<unordered_set>
#include<numeric>

using namespace std;

using ll = int64_t;

/// <summary>
/// 単純なcoutの時に使う
/// </summary>
#define co(a) cout<<a<<"\n"


/// <summary>
/// [beg, end)の範囲を，添え字indexでループするfor文に置換します
/// </summary>
#define rep(i,a) for(ll i=0; i<a; ++i)
#define reps(i, a, b) for(ll i = a; i < b; ++i)

/// <summary>
/// 迷路等で使う方向のベクトル
/// </summary>
const vector<ll> dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 };

/// <summary>
/// デバッグ時に使う
/// </summary>
#define DEBUG(x)     std::cout << #x << " : " << x << "\n"

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

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

	ll N, K;
	cin >> N >> K;

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

	sort (A.rbegin (), A.rend ());

	ll ans = 0;
	rep (i, K) {
		ans += A[i];
	}

	cout << ans << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; scanf("%lld", &x);
 
//int dxy[5] = {0, 1, 0, -1, 0};
// assign

vi tetra, odd_tetra;
vi table(1000001, INF), dp(1000001, INF);

void make_tetra();
void make_odd_tetra();


signed main()
{
    make_tetra();
    make_odd_tetra();

    Int(n);

    while (n) {
        cout << dp[n] << " " << table[n] << endl;
        cin >> n;
    }

    return 0;
}


void make_tetra()
{
    Rep(i, 181) {
        tetra.pb(i * (i + 1) * (i + 2) /6);
    }
    dp[0] = 0;
    Rep(x, 1000000) {
        int ret = INF;
        for (int i : tetra) {
            if (x < i) {
                break;
            } else {
                ret = min(ret, dp[x - i] + 1);
            }
        }
        dp[x] = ret;
    }
}

void make_odd_tetra()
{
    for (int i : tetra) {
        if (i % 2) {
            odd_tetra.pb(i);
            table[i] = 1;
        }
    }
    table[0] = 0;
    Rep(x, 1000000) {
        int ret = INF;
        for (int i : odd_tetra) {
            if (x < i) {
                break;
            } else {
                ret = min(ret, table[x - i] + 1);
            }
        }
        table[x] = ret;
    }
}

Measured memory_bytes: 18192
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,o,n) for(long long i = o;i<n;i++)
#define oneforall ios::sync_with_stdio(false);cin.tie(0);
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef vector<pair<long,long>> vpll;
typedef vector<pair<int,int>> vpii;
int main(){
	oneforall
	int n;
	cin>>n;
	int dp[100000];
	fill(dp, dp + 100000, 0);
	int a[100000];
	FOR(i, 0, n) { cin >> a[i]; };
	dp[1] = abs(a[1]-a[0]);
	FOR(i,2,n){
		dp[i] = min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
	}
	cout<<dp[n-1];
	return 0;
}

Measured memory_bytes: 1024
MAX = 1000
VMAX = 10000
n = int(input())
A = [int(i) for i in input().split()]
V = [False] * MAX
def solve():
    B = A[:]
    T = [0] * (VMAX + 1)
    B.sort()
    ans = 0
    s = min(VMAX, min(A))
    for i in range(n):
        T[B[i]] = i
    for i in range(n):
        if V[i] : continue
        cur = i
        S = 0
        m = VMAX
        an = 0
        while True:
            V[cur] = True
            an += 1
            v = A[cur]
            m = min(m, v)
            S += v
            cur = T[v]
            if V[cur] : break
        ans += min(S + (an - 2) * m, m + S + (an + 1) * s)
    print(ans)
solve()

Measured memory_bytes: 7884