akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

template <typename T>
void printv(const vector<T> &v) {
  int sz = v.size();
  for (int i = 0; i < sz; i++) {
    cout << v[i] << " \n"[i == sz - 1];
  }
}

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

  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }
  const int AMAX = 55;
  vector<vector<int>> dp(1 << n, vector<int>(AMAX, INF));
  dp[0][0] = 0;
  for (int i = 0; i < (1 << n); i++) {
    int pcnt = __builtin_popcount(i);
    for (int j = 0; j < AMAX; j++) {
      if (dp[i][j] == INF) continue;
      //cout << i << " " << j << " " << dp[i][j] << endl;
      int pre = 0;
      for (int k = 0; k < n; k++) {
        if ((i >> k) & 1) {
          pre++;
          continue;
        }
        int nxt = i | (1 << k);
        if (k % 2 == pcnt % 2) {
          // a[k] を使う
          if (a[k] < j) continue;
          dp[nxt][a[k]] = min(dp[nxt][a[k]], dp[i][j] + (k - pre));
        } else {
          // b[k] を使う
          if (b[k] < j) continue;
          dp[nxt][b[k]] = min(dp[nxt][b[k]], dp[i][j] + (k - pre));
        }
      }
    }
  }
  int ret = INF;
  for (int j = 0; j < AMAX; j++) {
    ret = min(ret, dp[(1 << n) - 1][j]);
  }
  cout << (ret == INF ? -1 : ret) << endl;
}


Measured memory_bytes: 67840
#include<iostream>
#include<algorithm>

int main() {
  int n;
  std::cin >> n;
  int color[9] = {};
  for (int i = 0;i < n;i++) {
    int a;
    std::cin >> a;
    if (a >= 3200) {
      color[8]++;
    } else {
      int idx = a / 400;
      color[idx]++;
    }
  }

  int flag = 0;
  for (int i = 0;i < 8;i++) {
    if (color[i] > 0)flag++;
  }
  int maxx = flag + color[8], minn = flag;
  if (color[8] == n)minn = 1;
  std::cout << minn << " " << maxx << std::endl;
}


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

#define ll long long
#define INF 99999999
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

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

    int left_max = 0;
    int right_min = N;

    rep(i,M)
    {
        int tmp_left, tmp_right;
        cin >> tmp_left >> tmp_right;
        left_max = max(left_max, tmp_left);
        right_min = min(right_min, tmp_right);
    }
    if( left_max > right_min ) cout << 0 << endl;
    else cout << right_min - left_max + 1 << endl;

}


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

int main(){
  int a1, a2, a3;
  cin>>a1>>a2>>a3;
  if(a1+a2+a3>=22)cout<<"bust"<<endl;
  else cout<<"win"<<endl;
}


Measured memory_bytes: 3620
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vvint c(3,vint(3));
    REP(i,3) REP(j,3) cin >> c[i][j];
    bool f = true;
    REP(i,2){
        if(c[i+1][0]-c[0][0]!=c[i+1][1]-c[0][1]||c[i+1][0]-c[0][0]!=c[i+1][2]-c[0][2]){
            f = false;
        }
    }
    if(f){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

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

using namespace std;

int C(int X, int N, vector<int>& p) {
    int d, min_d = numeric_limits<int>::max();

    vector<bool> mark(102);
    for (int& x: p)
        mark[x] = true;
    for (int i = 0; i < mark.size(); i++)
        if (!mark[i] && abs(X - i) < min_d) {
            min_d = abs(X - i);
            d = i;
        }
    return d;
}

int main() {
    int X, N;
    cin >> X >> N;
    vector<int> p(N);
    for (int i = 0; i < N; i++)
        cin >> p[i];
    cout << C(X, N, p);
    return 0;
}

Measured memory_bytes: 3636
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    char[]ss = S.toCharArray();
    
    int cou = 0;
    for(int i=0; i<3; i++) {
    	if(ss[i] == 'R') {
    		cou++;
    	}
    }
    if(cou != 2) {
    	System.out.println(cou);
    }else {
    	if(ss[1] != 'R') {
    		System.out.println(1);
    	}else {
    		System.out.println(cou);
    	}
    }
    }
}


Measured memory_bytes: 35696
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

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

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

  int ans = 0;
  while (true) {
    bool has_odd_num = false;
    for (int i=0; i<n; ++i) {
      if (a[i]%2 != 0) has_odd_num = true;
    }

    if (true == has_odd_num) break;
    for (int i=0; i<n; ++i) {
      a[i] /= 2;
    }
    ++ans;
  }

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

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

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	auto A=in(),B=in(),C=in(),D=in();
	if(A+B>C+D) out("Left");
	else if(A+B<C+D) out("Right");
	else out("Balanced");

	return 0;
}


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


using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(n) n.begin(),n.end()
#define eb emplace_back
#define endl "\n"

const ll maxn=3e5+50;

const ll maxx=1e13;
const ll mod=1000000007;
const ll mod1=998244353;
vector<ll> adj[maxn];

ll a[maxn];
ll b[maxn];
ll c[maxn];
ll d[maxn];
ll e[maxn];
ll n, m, q;
ll mx=0;
void dosth(ll id)
{
    if (id==n+1)
    {
        ll ans=0;
      for (int i=1;i<=q;i++)
      {
          if (e[b[i]]-e[a[i]]==c[i])
          {
              ans+=d[i];
          }

      }
      mx=max(mx,ans);
      return ;
    }
    for (int i=e[id-1];i<=m;i++)
    {
        e[id]=i;
        dosth(id+1);
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("test.txt","r",stdin);
    //freopen("FRAC.INP", "r", stdin);
    // freopen("WALKING.OUT", "w", stdout);

     cin>>n>>m>>q;
     e[0]=1;
     for (int i=1;i<=q;i++)
     {
         cin>>a[i]>>b[i]>> c[i]>>d[i];
     }
     dosth(1);
     cout <<mx;


}


Measured memory_bytes: 10744
function main(input) {
  const inputs = input.split('\n');
  const count = parseInt(inputs[0], 10);
  const heights =  inputs[1].split(' ').map(x => parseInt(x, 10));
  const mountains =[]
 
  pre_height = 0;
  for (i=0 ; i<count ; i++){
    //console.log((pre_height <= heights[i]))
    //console.log([pre_height , heights[i]])
    if( pre_height <= heights[i] ){
      mountains.push(heights[i]);
    }
    pre_height = Math.max(pre_height, heights[i])
  }
 
  console.log(mountains.length);
}
 
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 11468
#include<stdio.h>

int main(void){
  int a,b,i;
  int A = 0;
 scanf("%d %d",&a,&b);
  if(a == b){
    A = a*2;
  }else if(a > b){
    A +=a;
    if((a-1) >= b ){
      A += (a-1);
    }else{
      A += b;
    }
  }else{
    A += b;
    if((b-1)> a){
      A += (b-1);
    }else{
      A += a;
    }
  }
  printf("%d",A);
  return 0;
}

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

int gcd(int m, int n);
int lcm(int m,int n);

int main()
{
	int a[50], b[50];
	int set = 0;
	while( cin >> a[set] >> b[set])
		set++;

	for(int i = 0; i < set; i++)
		cout << gcd(a[i], b[i]) << " " << lcm(a[i], b[i]) << endl;

	return 0;
}

int gcd(int m, int n)
{
	int t;
	if(m < n){
		t = m;
		m = n;
		n = t;
	}

	t = m % n;
	while(t != 0){
		m = n;
		n = t;
		t = m % n;
	}
	return n;
}

int lcm(int m, int n)
{
	return ((m / gcd(m, n)) * n);
}

Measured memory_bytes: 3032
function main(input) {
  const S = input.toString().split('');
  let result = [];
  for (let i = 0; i < S.length; i++) {
    switch (S[i]) {
      case '0':
        result.push('0');
        break;
      case '1':
        result.push('1');
        break;
      case 'B':
        if (result.length > 0 ) { result.pop(); }
        break;
      default:
        break;
     }
  }
  console.log(result.join(''));
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 29536
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll n; cin >> n;
    vector<ll> a(n+1);
    vector<ll> b(n);
    REP(i, n+1) cin >> a[i];
    REP(i, n) cin >> b[i];

    ll count = 0;
    REP(i, n) {
        if (a[i] >= b[i]) {
            count += b[i];
            a[i] -= b[i];
            b[i] = 0;
        } else {
            count += a[i];
            b[i] -= a[i];
            a[i] = 0;
            if (a[i+1] >= b[i]) {
                count += b[i];
                a[i+1] -= b[i];
                b[i] = 0;
            } else {
                count += a[i+1];
                b[i] -= a[i+1];
                a[i+1] = 0;
            }
        }
        //for (auto elem : a) cout << elem << " "; cout << endl;
        //for (auto elem : b) cout << elem << " "; cout << endl;
        // cout << endl;
    }
    // for (auto elem : a) cout << elem; cout << endl;
    // for (auto elem : b) cout << elem; cout << endl;
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
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; }

//nはとりあえず一番でかい数を選ぶのがよさそう
//rはn/2に近い数かな
//nCr=nCn-rとパスカルの三角形的にそのような直観はとりあえず働く
int main(){
    int n;
    cin>>n;
    ll a[n],M=0,Mindex;
    rep(i,n){
        cin>>a[i];
        if(M<a[i]){M=a[i];Mindex=i;}
    }
    ll r=-1;int rindex;
    rep(i,n){
        if(i==Mindex) continue;
        int tmp=min(M-a[i],a[i]);
        if(r<tmp){
            r=tmp;
            rindex=i;
        }
    }

    cout<<M<<' '<<a[rindex]<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <climits>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i, a, b) for (int i = (a); i < static_cast<int>(b); i++)
#define FORR(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) FOR (i, 0, n)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
template <typename T>
void print(const vector<vector<T>> matrix);
template <typename T>
void print(const vector<T> vec);
template <typename Arg>
void print(const Arg arg);
template <typename Head, typename... Args>
void print(const Head head, const Args... args);
template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = INT_MAX / 2;
typedef pair<long long, long long> P;
using ll = long long;

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

    int N;
    cin >> N;
    map<ll, ll> map;
    ll tmp, sum = 0, ans = 0;

    map[0]++;
    rep (i, N) {
        cin >> tmp;
        sum += tmp;
        map[sum]++;
    }
    repall (i, map)
        ans += i.second * (i.second - 1) / 2;
    print(ans);
}

//---------------------------------------------
template <typename T>
void print(const vector<vector<T>> matrix) {
    repall (vec, matrix)
        print(vec);
}
template <typename T>
void print(const vector<T> vec) {
    repall (i, vec)
        cout << i << ' ';
    cout << '\n';
}
template <typename Arg>
void print(const Arg arg) {
    cout << arg << '\n';
}
template <typename Head, typename... Args>
void print(const Head head, const Args... args) {
    cout << head << " ";
    print(args...);
}


Measured memory_bytes: 12800
MOD = 998244353
N, K = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(K)]
 
dp = [0] * (N+1)
dp[1] = 1    #ok
for i in range(1, N):
  dp[i] += dp[i-1]   #as min k = 1, so carry this on to the next
  dp[i] %= MOD
  for l, r in LR:
    ll = i + l
    rr = i + r
    if ll <= N:
      dp[ll] += dp[i]    #yes ll is accesible
      dp[ll] %= MOD
    if rr < N:
      dp[rr+1] -= dp[i]    #not accessible and will get cancelled out when we take prefix sum
      dp[rr+1] %= MOD
 
print(dp[-1])

Measured memory_bytes: 16808
#include <bits/stdc++.h>
#define ll  long long int
#define pb push_back
#define ff first
#define ss second
#define vi vector<int>
#define br cout <<"\n";
#define all(x)  (x).begin(),(x).end()
#define rall(x)  (x).rbegin(),(x).rend()
#define tr(c,i) for(auto i :c)
#define pii pair< int,int >
#define fast_io() ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define pq priority_queue< pair<ll,pii> ,vector<pair<ll,pii>>,greater <pair<ll,pii>> >p;//container adapter makes ascending q
#define er(x) cout << x << " "
#define err(x,y) cout << x << " "<<y
const int MOD = 1e9+7;
const int N = 3500;
using namespace std;
clock_t time_p=clock();
void dem()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
int main()
{
    fast_io();
    int n ;
    cin >> n ;
    vector<int>vec ( n );
    for ( int &x: vec )cin >> x ;
    int cnt = 0 ;
    for ( int i =  1 ; i < n-1 ; ++i )
    {
        int x = vec[i-1]  , y = vec[i] ,z = vec[i+1];
        vector<int> v {x , y ,z };
        sort(all(v));
        cnt+= v[1] == y ;


    }
    cout << cnt ;
    return 0 ;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> ans(n, -1);
    for (int i = 0; i < m; ++i) {
        int s, c;
        cin >> s >> c;
        --s;
        if (ans[s] != -1 && ans[s] != c) {
            cout << -1 << endl;
            return 0;
        }
        ans[s] = c;
    }
    if (n != 1 && ans[0] == 0) {
        cout << -1 << endl;
        return 0;
    }
    if (ans[0] == -1) ans[0] = n == 1 ? 0 : 1;
    for (int i = 1; i < n; ++i) {
        if (ans[i] == -1) ans[i] = 0;
    }
    for (int i = 0; i < n; ++i) {
        cout << ans[i];
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include<stdio.h>
#include<stdlib.h>

int main(){
	int *A, n, i, j, cnt = 0, tmp, iMin, iTmp;;

	scanf("%d", &n);
	A = (int *)malloc(sizeof(int)*n);
	for (i = 0; i < n; ++i) scanf("%d", A+i);

	for (i = 0; i < n-1 ; i++) {
		iMin = iTmp = i;
		for (j = i; j < n; j++) {
			if (*(A + iMin) > *(A + j)) {
				iMin = j;
			}
		}
		if (iTmp != iMin) {
			tmp = *(A + i); *(A + i) = *(A + iMin); *(A + iMin) = tmp;
			cnt++;
		}
	}
	for (i = 0; i < n; i++) printf("%d%c", A[i], i < n - 1 ? ' ' : '\n');
	printf("%d\n", cnt);
	free(A);
	return 0;
}

Measured memory_bytes: 600
N=int(input())
S=[]
T=[]

for i in range(N):
   s,t=input().split()
   S.append(s)
   T.append(int(t))

X=input()
count=0

for j in range(N):
   if S[j]==X:
      for k in range(j+1,N):
         count+=T[k]
      break

print(count)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();

		int m = 1000000007;
		long a = powMod(10, n, m);
		long b = powMod(9, n, m);
		long c = powMod(8, n, m);
		long ans = a - b - b + c + m + m;
		ans %= m;
		System.out.println(ans);
	}

	/**
	 * xのn乗をmで割った余り
	 */
	static long powMod(long x, long n, int m) {
		assert 0 <= n : "n=" + n;
		assert 1 <= m : "m=" + m;

		if (m == 1) {
			return 0;
		}
		long r = 1;
		long y = x % m;
		if (y < 0) {
			y += m;
		}
		while (n > 0) {
			if ((n & 1) == 1) {
				r = r * y % m;
			}
			y = y * y % m;
			n >>= 1;
		}
		return r;
	}
}


Measured memory_bytes: 35716
n = int(input())
p = list(map(int, input().split()))

ans = 0
for i in range(1, n-1):
  if p[i-1] > p[i+1]:
    m = p[i+1]
    M = p[i-1]
  else:
    m = p[i-1]
    M = p[i+1]
  
  if m < p[i] < M:
    ans += 1

print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <bits/stdc++.h>
#include <math.h>

using namespace std;

int main(){
    long long a,b,x;
    cin>>a>>b>>x;
    int hoge=0;
    if(a%x==0) hoge=1;
    
    cout<<b/x - a/x + hoge<<endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iterator>
#include <functional>
#include <numeric>
using namespace std;

#define ll long long
#define forn(i,n)for(i=0;i<n;i++)
#define forc(i,c,n)for(i=c;i<=n;i++)
typedef list<ll> LST;
typedef vector<ll> VEC;
typedef map<ll, ll> MAP;

int main() {
	ifstream fin("Text.txt");
	ios_base::sync_with_stdio(false); cin.tie(0);

	ll i, j, q;
	ll n, m, p, k, t;
	ll a, b, c, d;
	ll x, y, z, l, r;
	ll one = 1, zero = 0, ans = 0;
	ll mod = 1000000007;
	string st1, st2, st3;
	char ch1, ch2, ch3;

	cin >> n;
	vector<vector<ll> > vc(n,vector<ll>(4));
	forn(i, n) {
		cin >> vc[i][0] >> vc[i][1] >> vc[i][2];
		vc[i][3] = vc[i][1]+vc[i][0];
	}
	forn(i, n) {
		forc(j, i + 1, n - 2) {
			vc[i][3] += vc[j][0] + ( vc[i][3] % vc[j][2] ? vc[j][2] - vc[i][3] % vc[j][2] : 0);
			vc[i][3] = max(vc[i][3], vc[j][1]+ vc[j][0]);
		}
	}
	forn(i, n) {
		cout << vc[i][3] << 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 RANGE(a,b,c) (a).begin()+b,(a).begin()+c // コンテナ a の 要素 b から c へのイテレータ
#define MOD 1000000007
#define INF 1000000000
typedef pair<int64_t, int64_t> PII;
typedef vector<int64_t> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;
#include <boost/integer/common_factor_rt.hpp> // gcd, lcm


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

int64_t A, B; cin >> A >> B;
cout << boost::integer::lcm(A, B) << endl;

}

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



Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String args[]){
		Scanner x=new Scanner (System.in);
		int a=x.nextInt();
		int a1[]=new int [a];
		for(int i=0;i<a;i++){
			a1[i]=x.nextInt();
			System.out.print(a1[i]);
			if(i<a1.length-1)
				System.out.print(" ");
		}
		System.out.println();
		for(int i=1;i<a1.length;i++){
			int key=a1[i];
			int j=i-1;
			while(j>=0&&a1[j]>key){
				a1[j+1]=a1[j];
				j--;
				a1[j+1]=key;
			}
			int d=0;
			for(int w=0;w<a1.length;w++){
				System.out.print(a1[w]);
				if(d>=0&&d<a1.length-1)
					System.out.print(" ");
				d++;
				if(d==a){
					System.out.println();
					d=0;
				}
			}
		}
	}
}


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

int n, m, k;
ll a[3030][3030], dp[3030][3030][4];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m >> k;
	for(int i=1;i<=k;i++){
		int x, y, v; cin >> x >> y >> v;
		a[x][y] = v;
	}

	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=0;k<=3;k++){
				dp[i][j][0] = max(dp[i][j][0], dp[i-1][j][k]);
				if(a[i][j]) dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][k] + a[i][j]);

				dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k]);
				if(a[i][j] && k <= 2) dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j-1][k] + a[i][j]);
			}
		}
	}

	cout << max({dp[n][m][3], dp[n][m][2], dp[n][m][1], dp[n][m][0]});
}

Measured memory_bytes: 358408
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	a, b, h = IR(3)
	print((a+b)*h//2)

if __name__ == '__main__':
    main()

Measured memory_bytes: 15708
#include <iostream>
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>
#define int long long
using namespace std;
signed main() {
    string S;
    cin>>S;
    bool ans=false;

    for(int i=0;i<S.size();i++){
        for(int j=i+1;j<S.size();j++){
            if(S[i]=='C'&&S[j]=='F'){
                ans=true;
            }
        }
    }
    if(ans==true){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}

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

int main(){
	int n,t,p=0,f=1;
	
	while(1){
		cin >> n;
		if(n==0) break;
		
		for(int i=0;i<n;i++){
			cin >>t;
			if(i==0){ cout << t; p=t;}
			else if(i==n-1 && t==p+1){
				cout << "-" << t;
			}
			else if(i==n-1 && t!=p+1){
				if(f==0){
					cout << "-" << p << " " << t;
				} else {
					cout << " " << t;
				}
			}
			else if(t!=p+1){
				if(f==1){
					cout << " " << t;
				} else {
					cout << "-" << p <<" "<<t;
				}
				p=t;
				f=1;
			}
			else { p++; f=0;}
		}
		cout << endl;
		p=0;t=0;f=1;
	}
}

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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()

const int MOD = 1e9 + 7;

void solve() {
  int n;
  cin >> n;
  if (n == 1) {
    cout << 1 << '\n';
    return;
  }
  map<int, int> m;
  for (int i = 2; i <= n; i++) {
    int tmp = i;
    for (int j = 2; j * j <= tmp; j++) {
      if (tmp % j == 0) {
        int cnt = 0;
        while (tmp % j == 0) {
          tmp /= j;
          cnt++;
        }
        m[j] += cnt;
      }
    }
    if (tmp > 1) m[tmp] += 1;
  }
  int ans = 1;
  for (auto &i : m) {
    (ans *= i.sc + 1) %= MOD;
  }
  cout << ans << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) solve();
}


Measured memory_bytes: 3612
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int,int>;

vector<int>bitSearch(int bit,int n){
    vector<int>S;
    rep(i,n)if(bit&(1<<i))S.push_back(i);
    return S;
}



int main(){
    int a,b,c;cin>>a>>b>>c;
    cout<<(a+b>=c?"Yes":"No");
}



Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func solve() {
	n, m := getInt(), getInt()
	xs := getIntSlice(m)
	sort.Ints(xs)

	ls := make([]int, m-1)
	for i := 1; i < m; i++ {
		ls[i-1] = abs(xs[i] - xs[i-1])
	}
	sort.Ints(ls)

	ans := 0
	for i := 0; i < m-n; i++ {
		ans += ls[i]
	}

	fmt.Fprintln(wr, ans)
}

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

// -----------------------------------------

const (
	inf = 1 << 60
	// mod = 1000000007
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func main() {
	maxBufSize := int(1e8)
	sc.Buffer(make([]byte, 4096), maxBufSize)
	sc.Split(bufio.ScanWords)
	solve()
	wr.Flush()
}

func getInt() (ret int) {
	sc.Scan()
	ret, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return
}

func getIntSlice(n int) (ret []int) {
	ret = make([]int, n)
	for i := range ret {
		ret[i] = getInt()
	}
	return
}

func getString() (ret string) {
	sc.Scan()
	ret = sc.Text()
	return
}

func getRunes() (ret []rune) {
	ret = []rune(getString())
	return
}


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

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

  if(0 <= x-r && x+r <= W && 0 <= y-r && y+r <= H)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;


  return 0;
}

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> prof(M);
  for (int i = 0; i < N; i++) {
    int a, b;
    cin >> a >> b;
    if (a > M) continue;
    prof[M-a].push_back(b);
  }
  priority_queue<int> q;
  ll ans = 0;
  for (int i = M-1; i >= 0; i--) {
    if (!prof[i].empty()) {
      for (auto p : prof[i]) {
        q.push(p);
      }
    }
    if (!q.empty()) {
      ans += q.top(); q.pop();
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 5632
#include <bits/stdc++.h>
//#include<iostream>
//#include<vector>
//#include<map>
//#include<math.h>
//#include<algorithm>

#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rep2(i,a,n) for(int i = (int)(a); i <= (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n-1); i > -1; i--)
#define rrep2(i,n,a) for(int i = (int)(n); i >= (int)(a); i--)

#define fi first
#define se second

using namespace std;

using ll = long long;
using v_int = vector<int>;
using v2_int = vector<v_int>;
using v_ll = vector<ll>;
using v2_ll = vector<v_ll>;
using v_string = vector<string>;
using v_bool = vector<bool>;
using v2_bool = vector<v_bool>;
using pii = pair<int, int>;
using mii = map<int, int>;

const double PI = 3.1415926535897932;
const int INF = (int)2e9;
const ll LINF = (ll)2e18;
const ll MOD = 1000000007;
const int dc[8] = {1, -1, 0,  0, 1, -1,  1, -1};
const int dr[8] = {0,  0, 1, -1, 1,  1, -1, -1};

template<typename T, typename U> inline
ostream& operator<<(ostream &o, pair<T,U> &p) {
    return o << "{" << p.first << "," << p.second << "}";
}
template<typename T> inline
istream& operator>>(istream &is, vector<T> &vec) {
    for(auto &v : vec) { is >> v; }
    return is;
}
template<typename T> inline
ostream& operator<<(ostream &os, vector<T> &vec) {
    for(auto &v : vec) { os << v << ",";}
    return os;
}
template<typename T> inline
ostream& operator<<(ostream &os, vector<vector<T> > &mat) {
    for(auto &row : mat) { os << row << endl; }
    return os;
}

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

int main(void)
{
    int n;
    cin >> n;
    string s,t;
    cin >> s >> t;
    
    rep(i,n) {
        cout << s[i] << t[i];
    }
    cout << endl;
    return 0;
} /*atcoder*/



Measured memory_bytes: 3604
#include<stdio.h>
#include<queue>
using namespace std;
struct node{
	int a;
	int b;
	int u;
	bool operator<(node c) const
	{
		return (long long)a*c.b>(long long)b*c.a;
	}
};
priority_queue<node> q;
int f[262144];
int a[262144],b[262144];
int fa[262144];
int findroot(int x)
{
	if(fa[x]==x)
	{
		return x;
	}
	return fa[x]=findroot(fa[x]);
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=2;i<=n;i++)
	{
		scanf("%d",&f[i]);
	}
	for(int i=1;i<=n;i++)
	{
		int v;
		scanf("%d",&v);
		if(v)
		{
			a[i]=1;
			b[i]=0;
		}
		else
		{
			a[i]=0;
			b[i]=1;
		}
		fa[i]=i;
	}
	for(int i=2;i<=n;i++)
	{
		node u;
		u.a=a[i];
		u.b=b[i];
		u.u=i;
		q.push(u);
	}
	long long ans=0;
	while(!q.empty())
	{
		node u=q.top();
		q.pop();
		if(a[u.u]!=u.a||b[u.u]!=u.b)
		{
			continue;
		}
		int ff=findroot(f[u.u]);
		ans+=(long long)a[ff]*b[u.u];
		a[ff]+=a[u.u];
		b[ff]+=b[u.u];
		fa[u.u]=ff;
		if(ff>1)
		{
			u.u=ff;
			u.a=a[ff];
			u.b=b[ff];
			q.push(u);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 8564
/*input
1 1
1000

*/

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char const *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  vector<int> v;
  int n, k; cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    int x; cin >> x; v.emplace_back(x);
  }

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

  int tot = 0;
  for (int i = 0; i < k; ++i) {
    tot += v[i];
  }
  cout << tot;

  return 0;
}

Measured memory_bytes: 3620
#include <stdio.h>
#include <string.h>

#define SQ(X) \
  ( (X) * (X) )

static int k_operafan[ 300 ][ 18 ];

static int
dpFSA (
  int req,
  int abl
  )
{
  int i;

  if ( req < 0 )        return ( 0 );
  else if ( req == 0 )  return ( 1 );
  else if ( abl <= 0 )  return ( 0 );
  else if ( ~k_operafan[ req ][ abl ] ) ;
  else
  {
    k_operafan[ req ][ abl ] = 0;
    for ( i = 0; req - i * SQ( abl ) >= 0; ++i )
    {
      k_operafan[ req ][ abl ] += dpFSA ( req - i * SQ( abl ), abl - 1 );
    }
  }

  return ( k_operafan[ req ][ abl ] );
}

/** Application main entry point. */
int
main (
  int     argc,
  char  * argv[ ]
  )
{
  memset ( k_operafan, -1, sizeof ( k_operafan ) );

  for ( ; ; )
  {
    int n;

    scanf ( "%d", &n );
    if ( !( n ) ) break ;

    printf ( "%d\n", dpFSA ( n, 17 ) );
  }

  return ( 0 );
}

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

void func(int N, int X, int T){
    int ans = (N / X) + ((N % X == 0) ? 0 : 1);
    cout << ans*T << endl;
}
int main() {
	int n,i,j;
    cin >> n >> i >> j;
    func(n,i,j);
    return 0;
}


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

#define ll long long

struct node
{
    int length = 0;
    bool dead = true;
    
    set<int> connected;
};

int n, m;
node graph[(int)1e5 + 1];

int pound(int index)
{
    if (graph[index].length > 0)
        return graph[index].length;
        
    int mx = 0;
    for (auto it : graph[index].connected)
        mx = max(mx, pound(it));
        
    return graph[index].length = mx + 1;
}

int main()
{
    cin >> n >> m;
    
    int x, y;
    for (int i = 0; i < m; ++i)
    {
        cin >> x >> y;
        graph[y - 1].connected.insert(x - 1);
        graph[x - 1].dead = false;
    }
    
    int mx = 0;
    for (int i = 0; i < n; ++i)
        if (graph[i].dead)
            mx = max(mx, pound(i));
            
    cout << mx - 1;
    
    return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cout<<setprecision(32);

	string s;
	cin>>s;
	int n = s.size();
	if(s[0] == s.back()){
		if(n&1){
			cout<<"Second\n";
		}else{
			cout<<"First\n";
		}
	}else{
		if(n&1){
			cout<<"First\n";
		}else{
			cout<<"Second\n";
		}
	}

	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mii map <int, int>
#define mll map <ll, ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define vd vector <double>
#define vll vector <ll>
#define fi first
#define se second
#define si set <int>
#define sll set <ll>
#define spii set <pii>
#define vpii vector <pair <int,int> >
#define vpll vector <pair <long long,long long> >
#define vvi vector <vector <int> >
#define vvpii vector <vector <pii > >
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()


using namespace std;
const ll INFLL = 1e18;
const int MAXN = 1e6+100;
const ll INF = 1e9;
const ll mod1=1e9+7;
const ll mod2=2e9+11;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef LOCAL
    freopen("a.in","r",stdin);
    #endif
    ll a,b,k;
    cin>>a>>b>>k;
    if (a>=k)
    {
        cout<<a-k<<" "<<b;
    } else
        cout<<0<<" "<<max(b+a-k,(ll)0);


}

Measured memory_bytes: 256
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

N, M = map(int, sys.stdin.readline().rstrip().split(" "))
As = list(map(int, sys.stdin.readline().rstrip().split(" ")))
BCs = []
for _ in range(M):
    B, C = map(int, sys.stdin.readline().rstrip().split(" "))
    BCs.append((B, C))

BCs.sort(key=lambda x: -x[1])
As.sort()
result = 0
for B, C in BCs:
    for _ in range(B):
        if len(As) == 0:
            print(result)
            exit(0)
        if As[0] <= C:
            As.pop(0)
            result += C
        else:
            print(result + sum(As))
            exit(0)
if len(As) == 0:
    print(result)
    exit(0)
else:
    print(result + sum(As))
    exit(0)


Measured memory_bytes: 25584
#include<stdio.h>
int main()
{
    int a,b,sum;
    scanf("%d %d",&a,&b);
    sum=a-b;
    if(sum-=sum*2){
         printf("%d",b+sum);
    }
    else{
        printf("%d",sum+b);
    }


    return 0;
}


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

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

const ll mod =  1000000007;  //ansを出力する時は (ans % mod + mod) % mod とする(負の剰余を正にする)
const int inf = 1e9;
const long long INF = 1LL << 60;   // INFの値は1152921504606846976

int main()
{
    ll n; cin >> n;
    ll x[n],y[n],h[n];
    ll ans_h = 0;
    rep(i,n) cin >> x[i] >> y[i] >> h[i];
    rep(i,101){
        rep(j,101){
            ll ans = 0;
            rep(k,n){
                if(h[k] > 0) ans = h[k] + abs(x[k] - i) + abs(y[k] - j);
            }
            bool ok = true;
            rep(k,n){
                if(h[k] != max((ll)0,ans - abs(x[k] - i) - abs(y[k] - j))){
                    ok = false;
                }
            }
            if(ok){
                cout << i << ' ' << j << ' ' << ans << endl;
                return 0; 
            }
        }
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#define rep(i, a, n) for(int i = a;i < n;i++)
using namespace std;
 
 
double dp[100010][50];
double ans[100010];
 
 
double pow2(int i){
    return pow(2, -i);
}
 
 
void makeDP(){
    dp[1][1] = 1;
    ans[1] = 1;
 
    rep(i, 1, 100005){
        rep(j, 0, 49){
            dp[i+1][j+1] = dp[i][j]*pow2(j);
            ans[i+1] += dp[i+1][j+1];
            dp[i+1][0] += dp[i][j]-dp[i+1][j+1];
        }
        ans[i+1] += ans[i];
    }
}
 
 
int main(){
    int n;
 
    makeDP();
     
    while(cin >> n, n) cout << fixed << ans[n] << endl;
 
    return 0;
}


Measured memory_bytes: 43220
using System;
using System.Linq;
using System.Collections.Generic;

namespace ABC
{
    class ProgramA
    {
        static void Main(string[] args)
        {
            var inputs = Console.ReadLine().Split(" ");
            var a = long.Parse(inputs[0]);
            var b = long.Parse(inputs[1]);

            if (b % a == 0)
                Console.WriteLine(a + b);
            else
                Console.WriteLine(b - a);
        }
    }
}


Measured memory_bytes: 27496
//{{{
#include <bits/stdc++.h>
using namespace std;
#define repX(a,b,c,x,...) x
#define repN(a) repX a
#define rep(...) repN((__VA_ARGS__,rep3,rep2,loop))(__VA_ARGS__)
#define rrep(...) repN((__VA_ARGS__,rrep3,rrep2))(__VA_ARGS__)
#define loop(n) rep2(i_,n)
#define rep2(i,n) rep3(i,0,n)
#define rep3(i,begin,end) for(int i=(int)(begin),i##_end=(int)(end);i<i##_end;++i)
#define rrep2(i,n) rrep3(i,n,0)
#define rrep3(i,begin,end) for(int i=(int)(begin-1),i##_end=(int)(end);i>=i##_end;--i)
#define foreach(x,a) for(auto&x:a)
using ll=long long;
const ll mod=(ll)1e9+7;
//}}}

int A[1000];
int B[1000];
int main(){
  int N, M;
  cin >> N >> M;
  rep(i, N) cin >> A[i];
  rep(i, M) cin >> B[i];
  sort(A, A + N); reverse(A, A + N);
  sort(B, B + M); reverse(B, B + M);
  ll ans = 1;
  int na = 0;
  int nb = 0;
  int fixed = 0;
  rrep(i, N * M + 1, 1){
    if(i == A[na] && i == B[nb]){
      na++;
      nb++;
    }else if(i == A[na]){
      na++;
      ans *= nb; ans %= mod;
    }else if(i == B[nb]){
      nb++;
      ans *= na; ans %= mod;
    }else{
      ans *= (na * nb - fixed); ans %= mod;
    }
    fixed++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define F first
#define S second
#define mod 1000000007
#define all(a) a.begin(),a.end()
#define dbg(n) cout<<#n<<' '<<n<<endl;
#define dbg_v(v) cout<<#v<<":";for(auto c:v) cout<<" "<<c; cout<<endl;
int power(ll x,ll y){ll res = 1;while(y>0){if(y&1)res = (res*x)%mod;y=y>>1;x=(x*x)%mod;}return res;}

void solve(){
	int n;
	cin>>n;
	ll a[n];
	for (int i = 0; i < n; i++)
	{
		cin>>a[i];
	}
	ll pre[n];
	pre[n-1]=a[n-1];
	for (int i = n-2; i >= 0; i--)
	{
		pre[i]=(pre[i+1]+a[i])%mod;
	}
	//dbg_v(pre);
	ll ans=0;
	for (int i = 0; i < n-1; i++)
	{
		ans=(ans+(a[i]*pre[i+1])%mod)%mod;
	}
	cout<<ans<<endl;
}

int main(){ 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);	
	int T=1;
	//cin>>T;
	while(T--)
		solve();
}



Measured memory_bytes: 6760
/*
 *  I wish I could travel by the road that crosses baby's mind,
 *  and out beyond all bounds;
 *  Where messengers run errands for no cause 
 *  between the kingdoms of kings of no history;
 *  Where Reason makes kites of her laws and flies them, 
 *  and Truth sets Fact free from its fetters.
 *                                           Rabindranath Tagore
 */

#include <bits/stdc++.h>
using namespace std;

#ifndef ORZ_EVERYBODY_BUT_ME
#define ORZ_EVERYBODY_BUT_ME
#endif

#ifndef SOCIALISM
#define SOCIALISM
#endif

typedef long long ll;
const size_t MAX_N = (300 + 5) << 1;
const ll HASH = 1e9 + 7;

char s[MAX_N][MAX_N];
ll hsh1[MAX_N][MAX_N], hsh2[MAX_N][MAX_N], power[MAX_N];

inline ll getHsh(ll hsh[MAX_N][MAX_N], int i, int l, int r) {
    if (!l) return hsh[i][r];
    return hsh[i][r] - hsh[i][l - 1] * power[r - l + 1];
}

int main() {
    int n, res = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%s", s[i]);
    for (int i = 0; i < n; ++i) {
        hsh1[i][0] = s[i][0];
        for (int j = 1; j < 2 * n; ++j) 
            hsh1[i][j] = hsh1[i][j - 1] * HASH + s[i][j % n];
    }
    for (int j = 0; j < n; ++j) {
        hsh2[j][0] = s[0][j];
        for (int i = 1; i < 2 * n; ++i)
            hsh2[j][i] = hsh2[j][i - 1] * HASH + s[i % n][j];
    }
    power[0] = 1;
    for (int i = 1; i < MAX_N; ++i) power[i] = power[i - 1] * HASH;
    for (int a = 0; a < n; ++a)
        for (int b = 0; b < n; ++b) {
            ll HSH1 = 0, HSH2 = 0;
            for (int i = 0; i < n; ++i) {
                HSH1 = HSH1 * power[i + 1] + getHsh(hsh1, (a + i) % n, b, i + b);
                HSH2 = HSH2 * power[i + 1] + getHsh(hsh2, (b + i) % n, a, i + a);
            }
            if (HSH1 == HSH2) ++res;
        }
    printf("%d\n", res);
    return 0;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long int n;
    cin>>n;
    long long int tmp=sqrt(n);
    for (long long int i=tmp;i>0;i--) {
        if (n%i==0) {
            cout<<(i-1)+((n/i)-1)<<endl;
            break;
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPP(i, n) for(int i = 1; i <= n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const ll MOD = 1000000007;
const int INF = 10e9;

int main() {
    int n,l; cin >> n >> l;
    vector<int> r(n);
    int s = 0;
    REPP(i,n) {
        r[i-1] = l+i-1;
        s += r[i-1];
    }
    vector<p> ans(n);
    REP(i,n) {
        ans[i].first = abs(r[i]);
        ans[i] .second = s-r[i];
    }
    sort(ALL(ans));
    cout << ans[0].second << endl;
    return 0;
}

Measured memory_bytes: 256
<?php
while (true) {
    $stdin = trim(fgets(STDIN));
    if ($stdin == 0) {
        break;
    }
    $words_list = array();
    for ($i = 0;$i < $stdin;$i++) {
        $words = trim(fgets(STDIN));
        list($a,$b) = explode(" ",$words);
        $words_list[$a] = $b;
    }
    $stdin = trim(fgets(STDIN));
    $result = "";
    for ($i = 0;$i < $stdin;$i++) {
        $str = trim(fgets(STDIN));
        if (array_key_exists($str,$words_list)) {
            $str = $words_list[$str];
        }
        $result .= $str;
    }
    echo $result."\n";
}
?>


Measured memory_bytes: 9412
class Heap
  def initialize(xs = [], &block)
    @que = xs
    @size = xs.size
    @cmp = block || lambda{ |a,b| a < b }
  end

  def push(x)
    i = @size
    while i > 0 do
      j = (i - 1) / 2
      break unless @cmp.call(x, @que[j])
      @que[i] = @que[j]
      i = j
    end
    @que[i] = x
    @size += 1
  end

  def replace
    m = @que[0]
    x = yield m
    i = 0
    while (ii = i * 2 + 1) < @size do
      j1 = ii
      j2 = ii + 1
      j1 = j2 if j2 < @size && @cmp.call(@que[j2], @que[j1])
      break unless @cmp.call(@que[j1], x)
      @que[i] = @que[j1]
      i = j1
    end
    @que[i] = x
    m
  end
end

def get_target(l, h, n, fs)
  r = 0
  fs.each do |f| r += h / f end

  # t0 = (l*h/r).ceil, t = (l*h/(r+n)).ceil
  lh = l * h
  t0 = (lh + r - 1) / r
  t = (lh + r + n - 1) / (r + n)

  raise if (t0 >= t + 2)

  t
end

n, k = gets.split.map(&:to_i)
as = gets.split.map(&:to_i)
fs = gets.split.map(&:to_i)
 
l = as.inject(:+) - k

if (l <= 0)
  p 0
  exit
end

# O(n * log(n))
afs = as.sort.zip(fs.sort.reverse).sort_by do |item| item[0]*item[1] end

# O(n * log(n))
sum = afs.map do |a, f|
  a
end
for i in (0...n-1)
  sum[i+1] += sum[i]
end
left = -1
right = n - 1
while right - left > 1 do
  mid = (left + right) / 2
  s = 0
  af = afs[mid][0] * afs[mid][1]
  #afs.each do |a,f| s += [af / f, a].min end
  for i in (0...n-1-mid)
    s += af / afs[n-1-i][1]
  end
  s += sum[mid]
  if(s > l)
    right = mid
  else
    left = mid
  end
end
m = right
# p ["m:",m]
if (m > 0)
  afs = afs.drop(m)
  n -= m
end
 
l = -k
max_f = 0
 
# O(n)
fs = afs.map do |a, f|
  l += a
  max_f = f if f > max_f
  f
end
 
# O(n)
t = get_target(l, l * max_f * max_f, n, fs)
# p ["t:", t]
max_af = 0
 
# O(n)
xs = fs.map do |f|
  l -= (a = t / f)
  af = a * f
  max_af = af if af > max_af
  [af + f, f]
end
if (l == 0)
  p max_af
else
  # O(n * log(n))
  xs.sort_by! do |item| item.first end
  q = Heap.new(xs) do |a,b| a.first < b.first end
 
  # assert: l <= 2*n
  # O(n * log(n))
  af, = q.replace do |a| [a[0] + a[1], a[1]] end while (l -= 1) >= 0
  p af
end



Measured memory_bytes: 63852