akhauriyash/Code-Regression huggingface dataset:
from collections import defaultdict
from collections import Counter

def aCb(n, r):
    ans = 1
    for x in range(1, n + 1):
        ans *= x
    for x in range(1, n - r + 1):
        ans //= x
    for x in range(1, r + 1):
        ans //= x
    return ans


def main():
    N, A, B = map(int, input().split())
    v_list = list(sorted(list(map(int, input().split()))))
    c_entire = Counter(v_list)
    total = sum(v_list[-A:])

    ans = 0
    for n in range(A, B + 1):
        p = v_list[-n:]
        if sum(p) * A == total * n:
            c = Counter(p)
            t = 1
            for k, v in c.items():
                t *= aCb(c_entire[k], v)
            ans += t

    print("{0:.7f}".format(total / A))
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
struct Edge {
  ll to;
  ll cost;
};
int main() {
  int N;
  cin >> N;
  bool t = false;
  for (int i = 1; i <= N; i++) {
    int price = i * 108;
    if (price /100 == N){
      cout << i << endl;
      return 0;
      t = true;
    }
  }
  if(!t){
    cout << ":(" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pb push_back
#define printV(v) for(int i=0;i<v.size();i++){cout << v[i]<< " ";} cout << endl
#define printRev(v) for(int i=v.size()-1;i >= 0;i--){cout << v[i] << " ";} cout << endl
#define sortV(v) sort(v.begin(),v.end())
#define revV(v) reverse(v.begin(),v.end())
#define FOR(i,from,n) for(int i=from;i<n;i++)
#define FOL(i,from,n) for(int i=from;i >= n;i--)
    
    ll a,b,c,d,e,f,g,n,m,k,t,x,h,w,q;
    ll mod = 1000000007;
    
    void solve(){
        string str;
        cin >> str;
        for(int i=0;i<3;i++){
            if(str[i]=='7'){
                cout <<"Yes";
                return;
            }
        }
        cout << "No";
    }
        

  
   
    int main(){
    ios_base::sync_with_stdio(false);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int cases = 1;
    //cin >> cases;
  
    while(cases--){ 
        solve();
    }

    return 0;

    }

Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
const int mod=1e9+7;
using LL=long long;
using std::cout;using std::endl;using std::cin;
using std::vector;using std::string;using std::set;using std::multiset;
using std::pair;using std::map;
using std::min;using std::max;
using std::make_pair;
std::ostream& operator<<(std::ostream& os,std::map<int,int>& obj){for(std::map<int,int>::iterator itr=obj.begin();itr!=obj.end();itr++){os<<itr->first<<"^"<<itr->second<<" ";}return os;}
std::ostream& operator<<(std::ostream& os,std::vector<std::map<int,int>>& obj){for(auto itr=obj.begin();itr!=obj.end();itr++){os<<*itr<<std::endl;}return os;}
std::ostream& operator<<(std::ostream& os,std::vector<int>& obj){for(auto itr=obj.begin();itr!=obj.end();itr++){os<<*itr<<endl;}return os;}

namespace ndifix{
template<class T>void sort(T &v){std::sort(v.begin(),v.end());}
}

int main(){std::cout << std::setprecision(10);
  double t,x;cin>>t>>x;cout<<t/x<<endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100005;
const int go[3][2] = {{2, 1}, {0, 2}, {1, 0}};
long long ans;
int n, x, y, m, cnte, cnt[3], siz, sum, flag, col[maxn], h[maxn];
struct edge_t { int to, next, w; } edge[maxn * 2];
void ins(int x, int y, int z) {
    edge[++cnte].to = y;
    edge[cnte].next = h[x];
    edge[cnte].w = z;
    h[x] = cnte;
}
void dfs(int now, int c) {
    ++cnt[col[now] = c];
    ++siz;
    for (int i = h[now]; i; i = edge[i].next) {
        sum += edge[i].w;
        if (col[edge[i].to] == -1) dfs(edge[i].to, go[c][edge[i].w]);
        else if (col[edge[i].to] != go[c][edge[i].w]) flag = 1;
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) col[i] = -1;
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d", &x, &y);
        ins(x, y, 1);
        ins(y, x, 0);
    }
    for (int i = 1; i <= n; ++i) {
        if (col[i] == -1) {
            flag = siz = sum = cnt[0] = cnt[1] = cnt[2] = 0;
            dfs(i, 0);
            if (flag) ans += (long long) siz * siz;
            else if (cnt[0] == 0 || cnt[1] == 0 || cnt[2] == 0) ans += sum;
            else ans += (long long) cnt[0] * cnt[1] + (long long) cnt[1] * cnt[2] + (long long) cnt[2] * cnt[0];
        }
    }
    printf("%lld", ans);
}


Measured memory_bytes: 6400
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int dp1[1000001], dp2[1000001];

void num(){
	for(int i = 1; i < 1000001; i++){
		dp1[i] = 1000000;
		dp2[i] = 1000000;
	}
	vector<int> v1, v2;
	for(int i = 1; i < 200; i++){
		int t = (i*i*i+3*i*i+2*i)/6;
		if(t > 1000000) break;
		v1.push_back(t);
		if(t%2) v2.push_back(t);
	}
	for(int i = 1; i < 1000001; i++){
		for(int j = 0; j < v1.size(); j++){
			if(i < v1[j]) break;
			dp1[i] = min(dp1[i],dp1[i-v1[j]]+1);
		}
		for(int j = 0; j < v2.size(); j++){
			if(i < v2[j]) break;
			dp2[i] = min(dp2[i],dp2[i-v2[j]]+1);
		}
	}
}

int main(){
	num();
	int n;
	while(scanf("%d", &n), n) printf("%d %d\n", dp1[n], dp2[n]);
}

Measured memory_bytes: 8864
/*
 author : arush gupta
 date :26.01.2020
 */
 #include<bits/stdc++.h>
 using namespace std;
 int main() {
 ios::sync_with_stdio(false);
 cin.tie(0);
 cout.tie(0);
float h,a;

cin >> h>>a;
cout << ceil(h/a)<<endl;

 return 0;
 }


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

int main(){
    long N;
    long p;
    long long int a[20002]={};
    long long int b[20002]={};

    cin >> N;
    a[1]=1;
    b[1]=20000*(N-1)+1;
    for(long i=2;i<=N;i++){
        a[i]=a[i-1]+20000;
        b[i]=b[i-1]-20000;
    }

    for(long i=0;i<N;i++){
        cin >> p;
        a[p]+=i;
        b[p]+=i;
    }

    for(long i=1;i<=N;i++){
        if(i!=1) cout << " ";
        cout << a[i];
    }
    cout << "\n";
    for(long i=1;i<=N;i++){
        if(i!=1) cout << " ";
        cout << b[i];
    }
    cout << "\n";

    return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
int exgcd(int a,int &s,int b,int &t){
	if(b==0){
		s=1;t=0;return a;
	}
	int k=exgcd(b,s,a%b,t);
	swap(s,t);
	t=t-a/b*s;
	return k;
}
int main(){
	int a,b,x,y;
	cin>>a>>b;
	int k=exgcd(a,x,b,y);
	cout<<x<<' '<<y<<"\n";
	return 0;
}


Measured memory_bytes: 3108
L, R = map(int, input().split())

num = 0
ans = (L * (L + 1)) % 2019
if (R - L) > 2020:
    ans = 0
else:
    for i in range(L, R):
        for j in range(i + 1, R + 1):
            ans = min(ans, (i * j) % 2019)
            if ans == 0:
                break
print(ans)

Measured memory_bytes: 3064
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

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

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

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する


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

    int n;
    cin >> n;
    if(n < 1200){
        cout << "ABC" << endl;
    }else if(n < 2800){
        cout << "ARC" << endl;
    }else{
        cout << "AGC" << endl;
    }
    return 0;
}


Measured memory_bytes: 888
# include <bits/stdc++.h>
# define rep(i, n) for(ll i = 0; i < (n); ++i)
# define reps(i, n) for(ll i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(ll i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(ll i=((int)(n)); i>0; --i)
# define ll long long
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
# define P pair<int, int>
# define mp make_pair
using namespace std;
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; }
ll lmax(ll a, ll b){if(a>= b) return a;return b;}
ll lmin(ll a, ll b){if(a>= b) return b;return a;}

int main() {
  int n; cin >> n;
  vector<double> v(n);
  rep(i, n) cin >> v[i];

  sort(ALL(v));
  double ans = v[0];
  rep(i, n-1){
    chmax(ans, (v[i+1]+ans)/2);
  }

  cout << ans << endl;
}


Measured memory_bytes: 3788
// Author : Syed Mujtaba
// Seek knowledge from the Cradle to the Grave !!
// https://www.linkedin.com/in/syed-mujtaba-064a5016a 

#include <bits/stdc++.h>
using namespace std;
#define int     long long
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
signed main()
{
	fast_io
	int n, w;
	cin >> n >> w;
	vector < int > wt(n), val(n);
	int dp[n + 1][100008] = {0};

	for(int i = 0; i < n; i++)
		cin >> wt[i] >> val[i];
	for(int i = 0; i <= 100000; i++) // base case
	{
		if(i == 0)
			dp[1][0] = 0;
		else if(i == val[0] && wt[0] <= w)
			dp[1][i] = wt[0];
		else
			dp[1][i] = 1e18;
	}
	for(int i = 2; i <= n; i++) // tabulation
	{
		for(int j = 0; j <= 100000; j++)
		{
			dp[i][j] = 1e18;
			dp[i][j] = dp[i - 1][j];
			if(j - val[i - 1] >= 0)
				dp[i][j] = min(dp[i][j], dp[i - 1][j - val[i - 1]] + wt[i - 1]);
		}	
	}
	int ans;
	for(int i = 0; i <= 100000; i++)
	{
		if(dp[n][i] <= w)
			ans = i;
	}
	cout << ans << endl;
}

Measured memory_bytes: 79232
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

use std::collections::HashMap;

fn main() {
    input! {
        n: usize,
        k: usize,
        aa: [usize;n]
    }
    let mut m: HashMap<usize,usize> = HashMap::new();
    for a in aa {
        *m.entry(a).or_insert(0) += 1;
    }
    let mut v: Vec<(usize,usize)> = m.into_iter().collect();
    v.sort_by_key(|x| x.1 );
    println!("{}",
        v.iter().rev().skip(k).map(|t| t.1).sum::<usize>());
}


Measured memory_bytes: 20632
#include <algorithm>
#include <array>
#include <climits> // INT_MAX, LONG_MAX, LLONG_MAX, UINT_MAX, ULONG_MAX, ULLONG_MAX
#include <cmath>
#include <cstdint>
#include <cstring> // memset
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

#define ALL(x) (x).begin(), (x).end()
#define INF 1e9
#define LOG(x) cout << #x << " = " << (x) << endl
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)

using namespace std;

int main() {
    long long x, y;
    cin >> x >> y;

    long long count = 0;
    long long current = x;
    while (current <= y) {
        count++;
        current *= 2;
    }

    cout << count << endl;
    
    return 0;
}


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

int main(){
  int N;
  cin>>N;
  string S;
  cin>>S;

  bool frag=true;
  if(N%2!=0){
    frag=false;
  }
  else{
    string T;
    for(int i=0;i<N/2;++i){
      T.push_back(S.at(i));
    }
    if(S!=T+T){
      frag=false;
    }
  }

  if(frag){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }

}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
B = []

def nanji(a,b): #aをbで何回割ることができるか
    t = a
    count = 0
    while t % b == 0:
        t = t / b
        count = count +1
    return(count)

for i in range(N):
    B.append(nanji(A[i],2))

print(min(B))

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

// --- SIEVE begin --- cut here ---

// sieve(upto) returns the list of prime numbers up to upto.
//   Size: upto(1e8).size() ... 5.7e6,  upto(1e9).size() ... 5.1e7
//   Performance: upto(1e8) ... 0.7sec,   upto(1e9) ... 9.2sec
vector<int> sieve(int upto) {
  vector<int> res;
  vector<bool> tbl(upto+1);
  ll lim = (int)(sqrt((double)upto)) + 1;
  for (int x = 2; x <= upto; x++) {
    if (tbl.at(x))  continue;
    res.push_back(x);
    if (x > lim)  continue;
    for (int y = x * 2; y <= upto; y += x) tbl.at(y) = true;
  }
  return res;
}

/*
  Prime Factorization
    Two versions:
      - prfac(n)
      - prfac(n, primes)
 */

vector<pair<ll, int>> prfac(ll n, const vector<int>& primes) {
  //      primes should contain prime numbers at least up to sqrt(n)
  vector<pair<ll, int>> res;
  ll x = n;
  for (ll p : primes) {
    if (x == 1)  break;
    if (p * p > x)  break;
    if (x % p != 0)  continue;
    int c = 1;
    x /= p;
    while (x % p == 0) {
      c += 1;
      x /= p;
    }
    res.push_back(make_pair(p, c));
  }
  if (x != 1)  res.push_back(make_pair(x, 1));
  return res;
}

vector<pair<ll, int>> prfac(ll n) {
  return prfac(n, sieve((int)(sqrt((double)n)) + 1));
}

/*
    List of divisors
      - getDivisors(n)
    Note: the results are NOT sorted
 */

// gdsub ... aux function used in getDivisors()
vector<ll> gdsub(int i, int n, auto fs) {
  if (i == n) { return vector<ll>({1}); }
  auto part = gdsub(i+1, n, fs);
  ll p  = fs.at(i).first;
  int r = fs.at(i).second;
  ll pp = p;    // pp = p^m, for m \in [1, r]
  int partOrigLen = part.size();
  for (int m = 1; m <= r; m++) {
    for (int j = 0; j < partOrigLen; j++) {
      part.push_back(pp * part.at(j));
    }
    pp *= p;
  }
  return part;
}

vector<ll> getDivisors(ll n) {
  auto fs = prfac(n);
  return gdsub(0, fs.size(), fs);
}

// --- SIEVE end --- cut here ---

ll power(ll p, ll r) {
  ll x = 1;
  for (int i = 0; i < r; i++) x *= p;
  return x;
}


int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N, P; cin >> N >> P;
  ll ans = 1;
  for (auto pr : prfac(P)) {
    ll p = pr.first;
    int r = pr.second;
    int rr = r / N;
    ans *= power(p, rr);
  }
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 1020
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
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;
}
int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;cin>>n>>m;
    int lim = 1e+5 + 10;
    vector<int> x(lim,0);
    vector<int> count_mod(lim,0), count_mod2(lim,0);
    rep(i,n){
        int a;
        cin>>a;
        x[a]++;
    }
    rep(i,lim){
        count_mod[i%m] += x[i]/2;
        count_mod2[i%m] += x[i]%2;
    }
    vector<bool> checked(m,false);
    int res=0;
    rep(i,m){
        if(i==0||i*2==m){
            res += count_mod[i]+count_mod2[i]/2;
            continue;
        }
        if(!checked[i]){
            DEBUG{
                printf("set: %d, %d\n",i,m-i);
                printf(" %d, %d\n",count_mod[i],count_mod2[i]);
                printf(" %d, %d\n",count_mod[m-i],count_mod2[m-i]);
            }
            int tmp = min(count_mod2[i], count_mod2[m-i]);
            res += tmp;
            if(count_mod2[i]<count_mod2[m-i]){
                tmp = count_mod2[m-i]-tmp;
                res += min(count_mod[i]*2, tmp);
                res += max((count_mod[i]*2-tmp)/2,0);
                res += count_mod[m-i];
            }else{
                tmp = count_mod2[i]-tmp;
                res += min(count_mod[m-i]*2, tmp);
                res += max((count_mod[m-i]*2-tmp)/2,0);
                res += count_mod[i];
            }
        }
        checked[i] = checked[m-i] = true;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 1408
def create_divisors(n):
  """
  自然数nの全ての約数を列挙したリストを作成する。

  Parameters
  ----------
  n : int
    自然数

  Returns
  -------
    divisors：list

  """
  divisors=[]
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      divisors.append(i)
      if i!=n//i:
        divisors.append(n//i)
  divisors.sort()
  return divisors
def factorization(n):
    """
    引数の値を素因数分解したリストを返す

    Parameters
    ----------
    n : int
        素因数分解したい自然数

    Returns
    -------
    retlist : list
        2以上の整数n => [[素因数, 指数], ...]の2次元リスト
    """
    retlist = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            retlist.append([i, cnt])

    if temp!=1:
        retlist.append([temp, 1])

    if retlist==[]:
        retlist.append([n, 1])

    return retlist
def isPrime(x):
  """
  xが素数か否か判定する。

  Parameters
  ----------
  x: int
      自然数

  Returns
  -------
      True:素数
      False:素数ではない
  """
  if x<2:
    return False
  for i in range(2,int(x**0.5)+1):
    if x%i==0:
      return False
  return True

n=int(input())
d=factorization(n)

p=[]
for i in range(len(d)):
  if isPrime(d[i][0]):
    p.append(d[i]) 

# print(p)
from collections import Counter
used=Counter()
ans=0
for i in range(len(p)):
  t=p[i][1]
  j=1
  t_sum=0
  while t>0 and t>=j:
    if used[p[i][0]**j]==0:
      ans+=1
    used[p[i][0]**j]+=1
    t-=j
    j+=1
print(ans)






Measured memory_bytes: 68380
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int N; vector<int> a[409]; map<vector<int>, int> d;
long long perm(int n, int k) {
	long long ret = 1;
	for (int i = n; i > n - k; i--) ret *= i;
	return ret;
}
vector<int> univec(vector<int> v) {
	vector<int> ret = v;
	for (int i = 0; i < 3; i++) {
		v.push_back(v[0]);
		v.erase(v.begin());
		ret = min(ret, v);
	}
	return ret;
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		a[i].resize(4);
		for (int j = 0; j < 4; j++) cin >> a[i][j];
		a[i] = univec(a[i]);
		d[a[i]]++;
	}
	long long ret = 0;
	for (int i = 0; i < N; i++) {
		d[a[i]]--;
		for (int j = i + 1; j < N; j++) {
			d[a[j]]--;
			for (int ri = 0; ri < 4; ri++) {
				a[i].push_back(a[i][0]); a[i].erase(a[i].begin());
				for (int rj = 0; rj < 4; rj++) {
					a[j].push_back(a[j][0]); a[j].erase(a[j].begin());
					map<vector<int>, int> e;
					e[univec({ a[j][1], a[j][0], a[i][1], a[i][0] })]++;
					e[univec({ a[j][0], a[j][3], a[i][2], a[i][1] })]++;
					e[univec({ a[j][3], a[j][2], a[i][3], a[i][2] })]++;
					e[univec({ a[j][2], a[j][1], a[i][0], a[i][3] })]++;
					long long res = 1;
					for (pair<vector<int>, int> k : e) {
						res *= perm(d[k.first], k.second);
						if (d[k.first] == 0) d.erase(k.first);
						if (k.first[0] == k.first[1] && k.first[1] == k.first[2] && k.first[2] == k.first[3]) {
							for (int l = 0; l < k.second; l++) res *= 4;
						}
						else if (k.first[0] == k.first[2] && k.first[1] == k.first[3]) {
							for (int l = 0; l < k.second; l++) res *= 2;
						}
					}
					ret += res;
				}
			}
			d[a[j]]++;
		}
	}
	cout << ret / 4 << endl;
	return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
 
int main(void){
  
  char s[100001];
  int an=0, i, d=0;
  
  scanf("%s", s);
  
  while(1){
    if(s[d] == '\0')
      break;
    d++;
  }
  
  for(i=0; i<d; i++){
    if(s[i-1]==s[i]){
      an++;
      if(s[i-1]=='0')
        s[i]='1';
      else s[i]='0';
    }
  }
  
  printf("%d\n",an);
}

Measured memory_bytes: 256
#include <stdio.h>

int main (void)
{
	int h, w;
	int i, j;

	while (1){
		scanf("%d %d", &h, &w);
		if (h == 0 && w == 0)break;

		for (i = 0; i < h; i++){
			for (j = 0; j < w; j++){
			printf("#");
			}
		printf("\n");
		}
		printf("\n");
	}
	
	return (0);
}

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

int N, cnt;

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		string S = to_string(i);
		if (S.size() % 2 == 1) cnt++;
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Washoum
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        inputClass in = new inputClass(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CVacation solver = new CVacation();
        solver.solve(1, in, out);
        out.close();
    }

    static class CVacation {
        public void solve(int testNumber, inputClass sc, PrintWriter out) {
            int n = sc.nextInt();
            int[] a, b, c;
            a = new int[n];
            b = new int[n];
            c = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
                b[i] = sc.nextInt();
                c[i] = sc.nextInt();
            }
            int[][] dp = new int[n][3];
            dp[0][0] = a[0];
            dp[0][1] = b[0];
            dp[0][2] = c[0];
            for (int i = 1; i < n; i++) {
                dp[i][0] = Math.max(dp[i - 1][1], dp[i - 1][2]) + a[i];
                dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][2]) + b[i];
                dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][0]) + c[i];
            }
            out.println(Math.max(dp[n - 1][0], Math.max(dp[n - 1][1], dp[n - 1][2])));

        }

    }

    static class inputClass {
        BufferedReader br;
        StringTokenizer st;

        public inputClass(InputStream in) {

            br = new BufferedReader(new InputStreamReader(in));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 47104
import numpy as np

N, K = map(int, input().split())
S = list(input()) + ['2']

blocks = []
cur = 1
seq = 0
for s in S:
    if int(s) == cur:
        seq += 1
    else:
        blocks.append(seq)
        cur = 1 - cur
        seq = 1
answer = 0
blocks = np.array(blocks)
for i in range(0, len(blocks), 2):
    answer = max(answer, blocks[i:i+2*K+1].sum())
print(answer)


Measured memory_bytes: 16724
def main():
    S = input()
    T = input()

    SR = S[::-1]
    TR = T[::-1]

    restore = False
    pos = 0
    r = ""
    for i in range(len(S)):
        r += SR[:i]
        for j, si in enumerate(SR[i:]):
            if si == '?':
                r += TR[pos]
                pos += 1
            elif si == TR[pos]:
                r += TR[pos]
                pos += 1
            else:
                break
            # print(i, si, pos)
            if pos == len(T):
                restore = True
                break
        if restore:
            r += SR[i+j+1:]
            break
        pos = 0
        r = ""

    if restore:
        r = r.replace('?', 'a')
        r = r[::-1]
        print(r)
    else:
        print('UNRESTORABLE')


if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
long long int power(int a,int b)
{
    if(b==0)
        return 1;
    long long int k=power(a,b/2);
    if(b%2==0)
        return ((k%M)*(k%M))%M;
    else
        return ((k%M)*(k%M)*(a%M))%M;
}
long long int fact(long long int n)
{
    if(n==1 || n==0)
        return 1;
    else
        return ((n%M)*(fact(n-1)%M))%M;

}
int div(int n)
{  int c=0;
    for(int i=1;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
          if(n/i==i)
            c++;
          else
            c+=2;
        }

    }

    
    return  c;
}
int func(int n)
{
    return (n*(n+1))/2;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     #ifndef ONLINE_JUDGE
 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
   #endif
   
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++)
        cin>>v[i];
    sort(v.begin(),v.end(),greater<int>());
    long long int sum=0;
    for(int i=0;i<n;i++)
    {
            if(i%2==0)
            sum=sum + v[i];
            else
                sum=sum-v[i];
    }
    cout<<sum;


 return 0;
}








Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)

using namespace std;
using ll = long long;

int main(){
    int a; string s;
    cin >> a >> s;
    if(a >= 3200) cout << s << endl;
    else cout << "red" << endl;

    return 0;
}

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

#define REP(i,s,n) for(int i=s; i<n; ++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false

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

int main(){

  int n;
  cin >> n;
  vector<ii> x(n);
  vector<int> ans(n);
  rep(i, n){
    cin >> x[i].first;
    x[i].second = i;
  }

  SORT(x);

  rep(i, n){
    if(i < n / 2) ans[x[i].second] = x[n / 2].first;
    else ans[x[i].second] = x[n / 2 - 1].first;
    //cout << x[i].first << "\t" << x[i].second << endl;
  }

  rep(i, n) cout << ans[i] << endl;

	return 0;
}


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

int main() {
    int a, b;
    cin >> a >> b;

    int a0 = 80 * a * 100 / 8;
    int a1 = 80 * (a + 1) * 100 / 8;
    int b0 = 80 * b * 100 / 10;
    int b1 = 80 * (b + 1) * 100 / 10;

    int c0 = (max(a0, b0) + 80 - 1) / 80;
    int c1 = (min(a1, b1) + 80 - 1) / 80;

    if (c0 < c1) {
        cout << c0 << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}

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

int main() {
	string S;
	int Q, T, F;
	cin >> S >> Q;
	bool a = false;
	deque<char> b;
	for (char& i : S) b.push_back(i);
	for (int i = 0; i < Q; i++) {
		cin >> T;
		if (T == 1) a = !a;
		else {
			char C;
			cin >> F >> C;
			if (F == 1) {
				if (a) b.push_back(C);
				else b.push_front(C);
			}
			else {
				if (a) b.push_front(C);
				else b.push_back(C);
			}
		}
	}
	if (a) {
		for (auto i = b.rbegin(); i != b.rend(); i++) cout << *i;
	}
	else {
		for (char& i : b) cout << i;
	}
}

Measured memory_bytes: 896
mojiretu = input()
K = int(input())

def n_th_singleton(n, moji):
    min = moji[0]
    min_nth_itimoji = []
    if n >= 2:
        nth_soeji = [j for j in range(len(moji)) if hikaku(moji[j], moji, n_th_singleton(n-1, moji))]
        #print(nth_soeji)
        min = moji[nth_soeji[0]]
        for i in nth_soeji:
            if (min >= moji[i]):
                min = moji[i]
                min_nth_itimoji.append(i)
    else:
        for i in range(len(moji)):
            if min >= moji[i]:
                min = moji[i]
                min_nth_itimoji.append(i)
    #print(min_nth_itimoji)
    return min_nth_itimoji

def hikaku(singleton, original_moji, soeji_list):
    for j in soeji_list:
        if singleton <= original_moji[j]:
            return False
    return True

def solution(moji, num):
    sucesseive_length = 0
    n = 1
    while sucesseive_length < num:
        n_list = n_th_singleton(n, moji)
        n_sorted_submoji_list = [moji[i:] for i in n_list]
        n_sorted_submoji_list.sort()
        not_choufuku_list = []
        #print(n_sorted_submoji_list)

        j = 0
        while j < len(n_sorted_submoji_list):
            for k in range(1, len(n_sorted_submoji_list[j])+1):
                if (n_sorted_submoji_list[j][:k] not in not_choufuku_list) and sucesseive_length < num:
                    sucesseive_length += 1
                    not_choufuku_list.append(n_sorted_submoji_list[j][:k])
                    #print(not_choufuku_list)
            if sucesseive_length == num:
                    #print(not_choufuku_list)
                return not_choufuku_list[-1]
            j += 1
        #print(sucesseive_length)
        n += 1


print(solution(mojiretu, K))

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

using namespace std;

typedef long long ll;
typedef pair<ll, string> pls;

const ll N = 50 + 3;
const ll M = 1e9 + 7;
const vector<string> S = {"A", "C", "G", "T"};

ll n;
unordered_set<string> violated;
map<pls, ll> mp;

void init() {
	for (string x: S) {
		violated.insert("AGC");
		violated.insert("GAC");
		violated.insert("ACG");
		violated.insert(x + "AGC");
		violated.insert(x + "GAC");
		violated.insert(x + "ACG");
		violated.insert("AGC" + x);
		violated.insert("GAC" + x);
		violated.insert("ACG" + x);
		violated.insert("A" + x + "GC");	
		violated.insert("AG" + x + "C");
	}
}

ll dfs(ll v, string s) {
	if (mp.count({v, s})) return mp[{v, s}];
	if (v == n) return 1;
	
	ll r = 0;
	for (string x : S) {
		x = s + x;
		if (!violated.count(x)) {
			x.erase(0, 1);
			r = (r + dfs(v + 1, x)) % M;
		}
	}
	
	return mp[{v, s}] = r;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	init();
	cin >> n;
	cout << dfs(0, "TTT");
	
	return 0;
}


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

const int N = 2e5+10;
string s[N];

int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>s[i];
	sort(s,s+n);
	cout<<(unique(s,s+n)-s)<<endl;
	return 0;
}

Measured memory_bytes: 9876
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

S = list(map(int, list(input())))[::-1]

l = [0]*2019
z = 1
tmp = 0
for i, s in enumerate(S):
	tmp += s*z
	l[tmp%2019] += 1
	z = z*10%2019

ans = 0
for v in l:
	ans += v*(v-1)//2
ans += l[0]

print(ans)

Measured memory_bytes: 13556
using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
 
class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        string[] answers = new string[n];
        for (int i = 0; i < n; i++)
        {
            int[] triangle = Console.ReadLine().Split(' ')
                                    .Select(val => int.Parse(val))
                                    .ToArray();
            answers[i] = IsRightAngle(triangle) ? "YES" : "NO";
        }
        for (int i = 0; i < n; i++)
        {
            Console.WriteLine(answers[i]);
        }
    }
    static bool IsRightAngle(int[] triangle)
    {
        Array.Sort(triangle);
        return Math.Pow(triangle[0], 2) + Math.Pow(triangle[1], 2) == Math.Pow(triangle[2], 2);
    }
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long ll;
typedef vector<ll> vll;

const int INF = 1000000000;

ll converBase(ll n, ll b) {
	ll x = 0;
	while (n >= b) {
		x += (n % b);
		n /= b;
	}
	x += n;
	return x;
}

int main() {FIN
    
    ll i, j, n, s, b = -1, x;
    cin >> n;
    cin >> s;
	for (i = 2; i * i <= n; i++) {
		x = converBase(n, i);
		if (x == s) {
			b = i;
			break;
		}
	}
	if (b == -1 and n > s) {
		for (i = ((ll)sqrt(n - s)) + 1; i >= 1; i--) {
			if ((n - s) % i == 0 and (((n - s) / i) > sqrt(n) - 1)) {
				j = ((n - s) / i) + 1;
				x = converBase(n, j);
				if (x == s) {
					b = j;
					break;
				}
			}
		}
	}
	if (n == s and b == -1)
		b = n + 1;
		
	cout << b << "\n";
	
    return 0;
}


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


int main(){
	const int INF = 1e9;
	int N;
	cin >> N;
	vector<int> X(N);
	for(int i=0; i<N; i++){
		cin >> X[i];
	}

	int ans = INF;
	for(int i=1; i<=100; i++){
		int s=0;
		for(int j=0; j<N; j++){
			int t = abs(X[j]-i);
			s += t*t;
		}
		ans = min(ans,s);
	}

	cout << ans << endl;

	return 0;

}



Measured memory_bytes: 256
/*Alohomora*/
#include<bits/stdc++.h>
#define ll         long long
#define fl(i,n)    for(i=0;i<n;i++)
#define fld(i,a,b) for(i=a;i>b;i--)
#define fli(i,a,n) for(i=a;i<n;i++)
#define inp(i,a,n) for(i=0;i<n;i++) {cin>>a[i];}
#define op(i,a,n)  for(i=0;i<n;i++) {cout<<a[i]<<" ";}
#define pb         push_back
#define mp         make_pair
#define mod1        987654319 
#define speedup    ios_base::sync_with_stdio(false),cin.tie(0)
using namespace std;
ll fact(ll n){ if(n==0){return 1;}return (n*fact(n-1))%mod1;}
ll power(ll x, ll y,ll mod){ll out = 1;while (y > 0){if (y & 1) out=(out*x)%mod;y = y>>1;x = (x*x)%mod;}return out%mod;}
ll inverse(ll a){return power(a,mod1-2,mod1);}
ll gcd(ll a,ll b){if(b==0){return a;}gcd(b,a%b);}
ll a[2000000];
void sieve(){ll i,j;fli(i,2,1000001){if(a[i]==0){for(j=i*i;j<1000001;j+=i){a[j]=1;}}}}
map<ll,vector<ll> >m1;
vector<ll>v1;
bool compar(const pair<ll,ll> &a, const pair<ll,ll> &b) 
{ 
    return (a.second < b.second);
} 
ll level[1000000];
vector<ll>root;
set<ll>s1;
void factorise(long long n) 
{ 
    while (!(n%2)) 
    { 
        n >>= 1; 
        s1.insert(2);
    } 
    for (long long i=3; i<=sqrt(n); i+=2) 
    { 
        while (n%i==0) 
        { 
        	s1.insert(i);
            n=n/i; 
        } 
    } 
  	if (n>2) 
  	{
       s1.insert(n);
	}
} 
void comp()
{
	ll l,i,j,k,q,n,d,m,temp=0,sum,count=0;
	cin>>n;
	vector<ll>v1;
	fl(i,n)
	{
		cin>>j;
		v1.pb(j);
	}
	int arr[1000001]={0};
	int arr1[1000001]={0};
	//cout<<"Yo"<<endl;
	for(int i=n;i>=1;i--)
	{
		temp=i;
		if(v1[temp-1]==1)
		{
			if(arr[i]%2==0)
			{
				arr1[i]=1;
			}
		}
		else
		{
			if(arr[i]%2==1)
			{
				arr1[i]=1;
			}
		}	
		
		if(arr1[i]==1)
		{
			for(int j=1;j<=sqrt(i);j++)
			{
				if(temp%j==0 && j!=temp/j)
				{
					arr[j]++;
					arr[temp/j]++;
				}
				else if(temp%j==0)
				{
					arr[j]++;
				}
			}

		}
		//cout<<"Yo"<<endl;
	}
	vector<ll>v2;
	for(int i=1;i<=n;i++)
	{
		if(arr1[i]==1)
		{
			v2.pb(i);
		}
		//cout<<"Yo"<<endl;
	}
	cout<<v2.size()<<"\n";
	fl(i,v2.size())
	{
		cout<<v2[i]<<" ";
		//cout<<"Yo"<<endl;
	}
	
} 
int main()
{
	speedup;
	ll i=0,t;
	ll n;
	//cin>>t;
	t=1;
	while(t--)
	{
	 comp();
	}
}

Measured memory_bytes: 14448
#include<bits/stdc++.h>
using namespace std;
int n,s=1;
int main()
{
	cin>>n;
	while(s*2<=n)
		s*=2;
	if(s==n)
	{
		cout<<"No";
		return 0;
	}
	cout<<"Yes"<<'\n'<<1+n<<' '<<3<<'\n';
	for(int i=2;i<n;i+=2)
		cout<<1<<' '<<i<<'\n'<<i<<' '<<i+1<<'\n'<<1<<' '<<i+n+1<<'\n'<<i+n+1<<' '<<i+n<<'\n';
	if(n%2==0)
		cout<<s<<' '<<n<<'\n'<<((s^n)^1)+n<<' '<<2*n;
	return 0;
}

Measured memory_bytes: 2304
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

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

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll x,y,z,k;
    cin >> x >> y >> z >> k;
    ll a[x],b[y],c[z];
    F0R(i,x) cin >> a[i];
    F0R(i,y) cin >> b[i];
    F0R(i,z) cin >> c[i];

    multiset<ll> m;
    multiset<ll> spare;
    F0R(i,x) m.insert(a[i]);
    int counterTemp = 0;
    while(m.size() > k)
      m.erase(m.begin());

    while(m.size()){
      ll temp = *m.begin();m.erase(m.begin());
      F0R(i,y) spare.insert(b[i] + temp);
      while(spare.size() > k)
        spare.erase(spare.begin());
    }



    while(spare.size()){
      ll temp = *spare.begin(); spare.erase(spare.begin());
      F0R(i,z) m.insert(c[i] + temp);
      while(m.size() > k)
        m.erase(m.begin());
    }

    int cnt = 0;
    for (auto i = m.crbegin(); i != m.crend(); i++) {
      cout << *i << endl;
      cnt ++;
      if(cnt == k) break;
    }

    return 0;
}

// read the question correctly (ll vs int)
// template by super1 derived from bqi343


Measured memory_bytes: 640
main = do
  [a,b,c] <- fmap (map read . words) getLine
  k <- readLn
  print (solve k a b c)


solve :: Int -> Int -> Int -> Int -> Int
solve k a b c =
  sum [m*2^k,a,b,c] - m
  where
    m = maximum[a,b,c]

Measured memory_bytes: 508
def calc(N, A, B, C):
    score = sum(B)
    for i in range(N - 1):
        if (A[i] + 1 == A[i + 1]):
            score += C[A[i] - 1]
    return score


N = int(input())
A = [int(s) for s in input().split()]
B = [int(s) for s in input().split()]
C = [int(s) for s in input().split()]
print(calc(N, A, B, C))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define ppll pair < pair<ll,ll> , pair<ll,ll> >

#define fr first
#define sc second

#define sw fr.fr
#define v fr.sc
#define w sc.fr
#define s sc.sc

using namespace std;

const ll N = 1010;
const ll W = 30100;
const ll Inf = 1e18;

ppll a[N];
ll Dp[N][W];

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

    for(ll i=1;i<=n;i++)    scanf("%I64d%I64d%I64d",&a[i].w,&a[i].s,&a[i].v) , a[i].sw = a[i].s + a[i].w ;

    sort(a+1,a+n+1);

    for(ll i=1;i<=n;i++)
        for(ll We=0;We<W;We++)
            Dp[i][We] = max( Dp[i-1][We] , We>=a[i].w ? a[i].v + Dp[i-1][min(We-a[i].w,a[i].s)] : -Inf );

    cout<<Dp[n][W-1];
}

Measured memory_bytes: 235520
#include <iostream>

using namespace std;

long long f(long long v, long long x) {
  return v / x;
}

int main() {
  long long a, b, x;
  cin >> a >> b >> x;

  const auto ans = f(b, x) - f(a, x) + (a % x == 0);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define INF 1000000000000
#define MOD 1000000007LL
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
typedef pair<int64_t, int64_t> PII;
typedef vector<int64_t> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;
typedef int64_t i64;


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

int N; cin >> N;
VI T(N), A(N); rep(i, 0, N) cin >> T[i] >> A[i];

rep(i, 1, N){
    i64 cof = max((T[i] + T[i-1] - 1) / T[i], (A[i] + A[i-1] - 1) / A[i]);

    T[i] *= cof;
    A[i] *= cof;
}

cout << T[N-1] + A[N-1] << endl;

}
// 書いて考える
// 境界，出力文字列 チェック
// 可読性優先．高速化次点．
// まずは全探索，分割統治，次にDP
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性，二分探索
// 存在判定：構成方法，入力の特徴
// gcd, lcm ,素因数分解．
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// テストケース作成は数表あり
// 実行エラー：vector添え字超え．0割り．



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int n;
    int a;
    cin >> n >> a;
    int l =  a;
    int all = a + n - 1;
    int ate;
    if(all < 0){
        ate = all;
    }
    else if(l > 0){
        ate = l;
    }
    else{
        ate = 0;
    }
    int result = (all + l) * (all - l + 1) / 2 - ate;
    cout << result << endl;
}

Measured memory_bytes: 256
/*================================================
# ~  file:B.cpp
# ~~ date:2020-03-09
# ~~~author: SoMnus_L
#        |everybody finds love,in the end|
#   人の運命か,人の希望は悲しみにつづられているね
=================================================*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define ll long long
const int N=1e6+10;
using namespace std;
typedef pair<int,int>PII;

ll n,a,b;
int main(){
 ios::sync_with_stdio(false);
   cin>>n>>a>>b;
    ll rem=n/(a+b);
    ll ans=a*rem;
    rem=n%(a+b);
    ans+=min(a,rem);
    cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    string s;
    cin>>a>>b;
    cin>>s;
    if (s[a]!='-'){
    cout<<"No"<<endl;
    return 0;
    }
    for (int i=0;i<a+b+1;i++)
        if (i!=a&&s[i]<'0'||s[i]>'9'){
            cout<<"No"<<endl;
            return 0;
        }
    cout<<"Yes"<<endl;
    return 0;
}

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

int n;

void dfs(string s, char mx) {
  if (s.size()==n) {
    cout<<s<<endl;
    return ;
  }
  for (char c='a'; c<=mx; c++) {
    dfs(s+c, ((c==mx)?(char)(mx+1):mx));
  }
  return ;
}


int main() {
  cin>>n;
  dfs("", 'a');
  return 0;
}


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

#define __INIT_CC__ ios::sync_with_stdio(false); \
	cin.tie(0);

#ifdef __WIN32__
	char getchar_unlocked() {return getchar();}
#endif

#define FOR(_i,_n,_m) for(int (_i)=(_n),_t=(_m);_i<(_t);++(_i))
#define FORN(_i,_n,_m) for(int (_i)=(_n),_t=(_m);_i<=(_t);++(_i))
#define FORD(_i,_n,_m) for(int (_i)=(_n),_t=(_m);_i>=(_t);--(_i))
#define RESET(_a,_value) memset(_a,_value,sizeof(_a))
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define ff first
#define ss second
#define mp make_pair
#define SIZE(_a) (int)_a.size()
#define VSORT(_a) sort(_a.begin(),_a.end())
#define SSORT(_a,_val) sort(_a,_a+(_val))
#define ALL(_a) _a.begin(),_a.end()
#define mt make_tuple
#define _get(_tuple,_i) get<_i>(_tuple)
#define eb emplace_back
 
using namespace std;

using vi = vector<int>;
using ii = pair<int,int>;
using vii = vector<ii>;
using ll = long long;
using ull = unsigned long long;
using pll = pair<ll,ll>;
using vpll = vector<pll>;
using vll = vector<ll>;
using pdd = pair<double,double>;
using vpdd = vector<pdd>;
template <typename T> using uset = unordered_set<T>;
template <typename T> using umultiset = unordered_multiset<T>;
template <typename K, typename V> using umap = unordered_map<K, V>;
template <typename K, typename V> using umultimap = unordered_multimap<K, V>;

const int dr[] = { 1, 0,-1, 0, 1, 1,-1,-1};
const int dc[] = { 0, 1, 0,-1, 1,-1,-1, 1};
const double eps = 1e-9;
const int INF = 0x7FFFFFFF;
const ll INFLL = 0x7FFFFFFFFFFFFFFFLL;
const double pi = acos(-1);

template <typename T> T take(queue<T> &O) {T tmp=O.front();O.pop();return tmp;}
template <typename T> T take(stack<T> &O) {T tmp=O.top();O.pop();return tmp;}
template <typename T> T take(priority_queue<T> &O) {T tmp=O.top();O.pop();return tmp;}
template <typename T>
inline bool inRange(const T& z, const T& a, const T& b){return a <= z && z <= b;}

void OPEN(const string& in = "input.txt", const string& out = "output.txt")
{
	freopen(in.c_str(), "r", stdin);
	freopen(out.c_str(), "w", stdout);
	return ;
}

//using sokokaleb's template v4.0

int n, m;
int arr[305][305];
bitset<305> ada;
int cnt[305];

int cek() {
	RESET(cnt, 0);
	FOR (i, 0, n) {
		FOR (j, 0, m) {
			if (ada.test(arr[i][j])) {
				++cnt[arr[i][j]];
				break ;
			}
		}
	}
	FOR (i, 0, m) {
		// cerr << cnt[i] << ",";
	}
	// cerr << endl;
	return *max_element(cnt, cnt + m);
}

int main(int argc, char** argv) {
	__INIT_CC__
	ada.set();
	cin >> n >> m;
	FOR (i, 0, n) {
		FOR (j, 0, m) {
			cin >> arr[i][j];
			--arr[i][j];
		}
	}

	int ans = cek();
	// cerr << " -- " << cek() << endl;
	FOR (i, 0, m - 1) {
		int ipos = distance(cnt, max_element(cnt, cnt + m));
		// cerr << ipos << endl;
		ada.set(ipos, 0);
		ans = min(ans, cek());
		// cerr << " -- " << cek() << endl;
	}

	cout << ans << "\n";
}


Measured memory_bytes: 640