akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define DEBUG(x)           cout << '>' << #x << ':' << x << endl;
#define forn(i,n)          for(int i=0;i<(int)n;++i)
#define for1(i,n)          for(int i=1;i<=(int)n;++i)
#define forr(i,n)          for(int i=(int)n-1;i>=0;--i)
#define forre(i,a,b)       for(int i=(int)b;i>=(int)a;--i)
#define fore(i,a,b)        for(int i=(int)a;i<=(int)b;++i)
#define input(i,arr)       for(int& i:arr)cin>>i;
#define output(i,arr)      for(int& i:arr)cout<<i<<" ";
#define for_each(arr)      for(auto& it:arr)
#define ff                 first
#define ss                 second
#define PI                 acos(-1.0)
#define all(a)             a.begin(),a.end()
#define rall(a)            a.rbegin(),a.rend()
#define Unique(a)          sort(all(a)),a.erase(unique(all(a)),a.end())
#define pb(x)              push_back(x)
#define eb(x)              emplace_back(x) 
#define ppb(x)             pop_back(x)
#define pf(x)              push_front(x)
#define ppf(x)             pop_front(x)
#define in(x,y)            insert({x,y})
#define Sort(a)            sort(a.begin(),a.end())
#define mem(arr,a)         memset(arr,a,sizeof arr)
#define ins(a)             insert(a)
#define max2(a,b)          max(a,b)
#define max3(a,b,c)        max(a,max(b,c))
#define max4(a,b,c,d)      max(a,max3(b,c,d))
#define min2(a,b)          min(a,b)
#define min3(a,b,c)        min(a,min(b,c))
#define min4(a,b,c,d)      min(a,min3(b,c,d))
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<char> vc;
typedef vector<double> vd;
/*inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void Set(int & n, int b) { n |= two(b); }
inline void Reset(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }*/
/*int fx1[]={+1,-1,+0,+0};
int fy1[]={+0,+0,+1,-1};
int fx2={+0,+0,+1,-1,-1,+1,-1,+1};
int fy2={-1,+1,+0,+0,+1,+1,-1,-1};
*/

ll a,b,c,n,ans,cn1,cn2,cn3,t;
string s,s1,s2;


int main()
{
    FIO;
    // #ifndef ONLINE_JUDGE
  //  freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
  //  #endif
    cin>>a;
    vector<int>v(a);

    int sum=0;
    int mn=103,mx=-1;
    for(int i=0;i<a;i++)
    {
    	cin>>v[i];
    	sum+=v[i];
    	mn=min(mn,v[i]);
    	mx=max(mx,v[i]);
    	
    }

    //sort(v.begin(),v.end());
   // cout<<sum<<endl;
    
   // cout<<b<<endl;
    b=sum/a;
    
    for(int i=0;i<a;i++){
    	ans+=abs(b-v[i])*abs(b-v[i]);
    }
    b=sum/a+1;
    ll ans1=0;
    for(int i=0;i<a;i++){
    	ans1+=abs(b-v[i])*abs(b-v[i]);
    }

   // cout<<ans<<endl;
    b=(mn+mx)/2;
    ll ans2=0;
    for(int i=0;i<a;i++){
    	ans2+=abs(b-v[i])*abs(b-v[i]);
    }
    cout<<min(ans,min(ans1,ans2))<<endl;
    


    
   	
    #ifdef ONLINE_JUDGE
    cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
    #endif
   return 0;
}
 


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

int main() {
  int N,K,sum;
  cin >> N >> K;
  sum = 0;
  for (int i = 0 ; i < N ; i++){
    int x;
    cin >> x;
    if (x < K && K < x*2) sum += (K-x)*2;
    else if (x < K) sum += x*2;
    else sum += (x-K)*2;
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<numeric>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n;i++)
#define ll long long
#define modbig (10*10*10*10*10*10*10*10*10+7)
using namespace std;

int main(){
  string s;
  cin>>s;
  cout<<s.substr(0,s.length()-8);
}


Measured memory_bytes: 256
INF = int(1e10)

N = int(input())
A, B, C = [None], [None], [None]

for _ in range(N):
    a, b, c = list(map(int, input().split()))
    A.append(a)
    B.append(b)
    C.append(c)

# compute DP
DP = [[0 for _ in range(3)] for _ in range(N + 1)]
DP[1][0] = A[1]
DP[1][1] = B[1]
DP[1][2] = C[1]

# day 2 to N
for d in range(2, N + 1):
    # print(DP[d-1], DP[d])
    DP[d][0] = max(DP[d-1][1], DP[d-1][2]) + A[d]
    DP[d][1] = max(DP[d-1][0], DP[d-1][2]) + B[d]
    DP[d][2] = max(DP[d-1][0], DP[d-1][1]) + C[d]

print(max(DP[N][:]))


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

#define ll long long
using namespace std;

ll x, y, z, a, b, c, _ap, _bp, _cp, N, ans, ara[ 200000 + 3 ], hi, flag;
vector <ll> adj[ 2003 ];
ll _a[ 100003 ], _b[ 100003 ], _c[ 100003 ], _t[ 300005 ];

int main()
{
  cin >> x >> y >> a >> b >> c;
  z = c;
  
  for (ll i=0; i<a; i++)
    cin >> _a[ i ];
  
  for (ll i=0; i<b; i++)
    cin >> _b[ i ];
  
  for (ll i=0; i<c; i++)
    cin >> _c[ i ];
 
  sort( _a, _a + a, greater< ll >());
  sort( _b, _b + b, greater< ll >());
  
  ll i = 0, in = 0;
  for ( ; i<x; i++) 
    _t[ in++ ] = _a[ i ];
  
  i = 0;
  for ( ; i<y; i++) 
    _t[ in++ ] = _b[ i ];
  
  i = 0;
  for ( ; i<c; i++) 
    _t[ in++ ] = _c[ i ];
  
  sort( _t, _t + in , greater< ll >());
  
  for (i=0; i<x+y; i++)
    ans += _t[ i ];
  
  cout << ans << "\n";
  
  return 0;
}


Measured memory_bytes: 6400
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<numeric>
#include<utility>
#include<queue>

using namespace std;

typedef long long int ll;
const int INF = 1<<30;
const long long LINF = 1LL<<60;

int main(){
    ll n, d, a, ans = 0;
    cin >> n >> d >> a;
    vector<pair<ll, ll>> x(n);
    for(int i = 0; i < n; i++){
        cin >> x[i].first >> x[i].second;
    }
    sort(begin(x), end(x));
    for(int i = 0; i < n; i++){
        x[i].second = (x[i].second + a - 1) / a;
    }
    d = d * 2 + 1;
    ans += x[0].second;
    ll dm = x[0].second;
    queue<pair<ll, ll>> q;
    q.push({x[0].first + d, -x[0].second});
    for(int i = 1; i < n; i++){
        ll p = x[i].first, h = x[i].second;
        auto qu = q.front();
        while(!q.empty() && qu.first <= p){
            q.pop();
            dm = max(0LL, dm + qu.second);
            qu = q.front();
        }
        if(dm >= h){
            continue;
        }
        ans += h - dm;
        q.push({p + d, -(h - dm)});
        dm = h;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    int N;
    cin >> N;
    map<int,int> A;
    map<int,int> B;
    rep(i,N) {
        int M;
        cin >> M;
        if (i % 2 == 0) {
            A[M]++;
        } else {
            B[M]++;
        }
    }
    if (A.size() == 1 && A.size() == B.size() && begin(A)->first == begin(B)->first) {
        cout << N/2 << endl;
        return 0;
    }
    set<pair<int,int>, greater<pair<int,int>>> C;
    for (auto x : A) C.insert({x.second, x.first});
    set<pair<int,int>, greater<pair<int,int>>> D;
    for (auto x : B) D.insert({x.second, x.first});
    pair<int, int> x = *begin(C), y = *begin(D);
    if (x.second == y.second) {
        pair<int, int> x2 = *(++begin(C)), y2 = *(++begin(D));
        if (x.first + y2.first > x2.first + y.first) {
            cout << N - x.first - y2.first << endl;
        } else {
            cout << N - x2.first - y.first << endl;
        }
    } else {
        cout << N - x.first - y.first << endl;
    }
}

Measured memory_bytes: 9600
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    ll N, M, X;
    cin >> N >> M >> X;
    vector<ll> C(N);
    vector<vector<ll>> A(N, vector<ll>(M));
    rep(i, N) {
        cin >> C[i];
        rep(j, M) cin >> A[i][j];
    }
    ll res = LINF;
    for(int bit = 0; bit < (1 << N); bit++) {
        vector<ll> all(M);
        ll cost = 0;
        for(int i = 0; i < N; i++) {
            if(bit & (1 << i)) {
                rep(j, M) all[j] += A[i][j];
                cost += C[i];
            }
        }
        int flag = 1;
        rep(i, M) {
            if(all[i] < X)
                flag = 0;
        }
        if(flag)
            res = min(cost, res);
    }
    if(res == LINF)
        res = -1;
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>

using namespace std;

struct before_main{before_main(){cin.tie(0); ios::sync_with_stdio(false);}} before_main;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

typedef long long ll;
int const inf = 1<<29;

int N, maxw;

void solve(vector<string>& v) {

  auto get_top_plus = [&](int sy, int x) {  // '+'????????????sy??\?????§????????????
    REP(y, sy, v.size()) {
      if(v[y][x] == '.' && isalpha(v[y][x+1])) {
        return y;
      }
    }
    return -1;
  };

  auto find_down_through = [&](int sy, int& ty, int x) {
    REP(y, sy+1, v.size()) {
      // '.'??§????????????????????¨(?¬????????????????????????¨???????????????)
      if(v[y][x] == '.' && isalpha(v[y][x+1])) {
        ty = y;
        return true;
      }
      else if(v[y][x] != '.') {
        break;
      }
    }
    return false;
  };

  // ??????????????????????±????????????????????????????????????????+??§?§???????+??§?????????????????????????????????|??§?????????
  rep(x, maxw) {
    int y = 0;
    while(1) {
      y = get_top_plus(y, x);
      if(y == -1) { break; }
      v[y][x] = '+';
      int ny = -1;
      while(find_down_through(y, ny, x)) {
        v[ny][x] = '+';
        REP(i, y+1, ny) {
          v[i][x] = '|';
        }
        y = ny;
      }
      if(ny == -1) {
        y++;
      }
    }
  }

  rep(i, N) {
    for(int j=0;!(j && isalpha(v[i][j-1]) && v[i][j] == ' '); j++) {
      if(v[i][j] == '.') cout << ' ';
      else cout << v[i][j];
    }
    cout << endl;
  }
}

int main() {

  for(; cin >> N;) {
    vector<string> v(N);
    maxw = 0;
    rep(i, N) { cin >> v[i]; maximize(maxw, v[i].size()); }
    maxw++;
    rep(i, N) { v[i].resize(maxw, ' '); }
    solve(v);
  }
  
  return 0;
}

Measured memory_bytes: 4184
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<functional>
#include<climits>
#include<utility>
#include <iomanip>
#include<map>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;

#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define FOR(i,s,e) for (int i = int(s); i < int(e); i++)
#define REP(i,x) FOR(i,0,x)
#define CLR(a) memset((a), 0 ,sizeof(a))


const int MOD = 1e+9+7;
const double PI  = acos(-1.0);

int main(){
	int n,in;
	cin>>n;
	vi x;
	REP(i,n){
		cin>>in;
		x.push_back(in);
	}
	sort(x.begin(), x.end());
	int dup=0;
	REP(i,n-1){
		if(x[i]==x[i+1]) dup++;
	}
	dup+=dup%2;
	cout<<(n-dup)<<"\n";
}


Measured memory_bytes: 892
#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const ll INF = 1e18;
/* テンプレートここまで */

int main() {
  string s; cin >> s;
  ll d = s.size();
  bool nine = true;
  FOR(i,1,d){
    if(s[i] != '9') nine = false;
  }
  cout << 9*(d-1) + (nine ? s[0]-'0' : (s[0]-'0')-1) << endl;
}

Measured memory_bytes: 256
s=input()
ans=[-1,-1]
for i in range(len(s)-1):
    if s[i]==s[i+1]:
        ans=[i+1,i+2]
        break
    else:
        if i<=len(s)-3:
            if s[i]==s[i+2]:
                ans=[i+1,i+3]
                break
print(*ans)

Measured memory_bytes: 3188
W,H,x,y,r = map(int, input().split())
x_right = x + r
x_left = x - r
y_above = y + r
y_below = y - r

if (x_right <= W) and (x_left >= 0) and (y_above <= H) and (y_below >= 0):
    print("Yes")
else:
    print("No")



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

typedef long long ll;
const int N = 10005;
const int M = 1000000007;

int n, m;
typedef int wtype;
struct Edge { int v; wtype d, c; };
vector<Edge> e[N];
wtype dist[N], cost[N];
int pre[N];
bool vis[N];
int SPFA(int src) {
  memset(dist, 0x3f, sizeof(dist)); dist[src] = 0;
  memset(cost, 0x3f, sizeof(cost)); cost[src] = 0;
  memset(vis, 0, sizeof(vis)); vis[src] = true;
  stack<int> que; que.push(src);
  while (!que.empty()) {
    int u = que.top(); que.pop();
    vis[u] = false;
    for (int i = 0; i < (int)e[u].size(); i++) {
      int v = e[u][i].v; wtype d = e[u][i].d, c = e[u][i].c;
      if (dist[v] > dist[u] + d || (dist[v] == dist[u] + d && cost[v] != 0x3f3f3f3f && cost[v] > c)) {
        dist[v] = dist[u] + d; cost[v] = c;
        if (!vis[v]) { vis[v] = true; que.push(v); }
      }
    }
  }
  int ret = 0;
  for (int i = 1; i <= n; i++) { ret += cost[i]; }
  return ret;
}

int main() {
  while (scanf("%d%d", &n, &m), n) {
    for (int i = 1; i <= n; i++) { e[i].clear(); }
    for (int i = 0, u, v, d, c; i < m; i++) {
      scanf("%d%d%d%d", &u, &v, &d, &c);
      e[u].push_back((Edge) {v, d, c});
      e[v].push_back((Edge) {u, d, c});
    }
    printf("%d\n", SPFA(1));
  }
}

Measured memory_bytes: 5036
#include<iostream>
using namespace std;
int minimalMoney;
int numOfBook,numOfA,underIndex;
int num[20][20];
int dp[20];



int calculate(){
	int temp;
	for(int i=1;i<=numOfA;i++){
		temp=0;
		for(int j=1;j<=numOfBook;j++){
			if(dp[j]==1){
				temp+=num[j][i];
			}
		}
		if(temp<underIndex)	{
			return -1;
		}
	}
	temp=0;
	for(int i=1;i<=numOfBook;i++){
		if(dp[i]==1)
		temp+=num[i][0];
	}
	return temp;
}

void decide(int start,int end){
	if(start>end){
		int temp=calculate();
		if(temp==-1)return;
		minimalMoney=temp<minimalMoney?temp:minimalMoney;
	}
	else{
		dp[start]=0;
		decide(start+1,end);
		dp[start]=1;
		decide(start+1,end);
	}
}

int main(){
	cin>>numOfBook>>numOfA>>underIndex;
	for(int i=1;i<=numOfBook;i++){
		for(int j=0;j<=numOfA;j++){
			cin>>num[i][j];
		}
		dp[i]=1;
	}
	minimalMoney=1;
	for(int i=1;i<=numOfBook;i++){
		minimalMoney+=num[i][0];
	}
	int temp=minimalMoney;
	decide(1,numOfBook);
	if(temp==minimalMoney){
		cout<<-1;
	}
	else{
		cout<<minimalMoney;
	}
	
	
	
	
	
	
	
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>
#include <ctime>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

const ll SZ = 2010, INF = 1e9 * 1e9;

ll n;
vector<ll> vec;

map<tuple<ll, ll, ll, ll>, ll> mp;
ll ans(ll ind1, ll x1, ll ind2, ll x2) {
	if (mp.find({ ind1, x1, ind2, x2 }) != mp.end()) {
		return mp[{ ind1, x1, ind2, x2 }];
	}

	if (ind1 == ind2 - 1) {
		return 0;
	}

	ll cur = INF;
	for (int i = ind1 + 1; i <= ind2 - 1; i++) {
		cur = min(cur, ans(ind1, x1, i, x1 + x2) + ans(i, x1 + x2, ind2, x2) + (x1 + x2) * vec[i]);
	}

	mp[{ ind1, x1, ind2, x2 }] = cur;
	return cur;
}

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

	vec.resize(n);

	for (auto &cur : vec) cin >> cur;

	cout << ans(0, 1, n - 1, 1) + vec[0] + vec.back();

	return 0;
}

Measured memory_bytes: 24000
#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<tuple>
#include<algorithm>
#include<numeric>
#include<math.h>

#define REPS(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define print(x) cout << #x << " = " << x << endl;

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;


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

	string str = to_string(N);
	
	bool bCheck = true;
	for (int i = 1; i < str.size(); i++) {
		if (str[i] != '9') bCheck = false;
	}

	if (bCheck) cout << 9 * (str.size() - 1) + (str[0] - '0') << endl;
	else if (str.size() == 1) cout << N << endl;
	else cout << 9 * (str.size() - 1) + (str[0] - '0') - 1 << endl;

	return 0;
}

Measured memory_bytes: 256
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

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

fn main() {//b棟f階のr番目の部屋にv人が追加

    const RSIZE: usize = 10;
    const FSIZE: usize = 3;
    const BSIZE: usize = 4;
    let mut uni: [[[i32; RSIZE]; FSIZE]; BSIZE] = [[[0; RSIZE]; FSIZE]; BSIZE];
    // println!("{:?}", uni);
    let n:i32 = read();
    for _i in 0..n {
        let input:Vec<i32> = read_vec();
        let b:usize = (input[0] - 1) as usize;
        let f:usize = (input[1] - 1) as usize;
        let r:usize = (input[2] - 1) as usize;
        let v:i32 = input[3];
        uni[b][f][r] += v;
    }

    for i in 0..BSIZE {
        for j in 0..FSIZE {
            for k in 0..RSIZE {
                print!(" {}", uni[i][j][k]);
            }
            println!("");
        }
        if i != BSIZE - 1 {
            println!("####################");
        }
    }

}


Measured memory_bytes: 5024
#include <cmath>
#include <iostream>
#include <string>
#include <vector> 
#include <algorithm>
#include <numeric>
#include <map>   
#include <stdio.h>

#define FOR(i,a,b) for(i=(a);i<(b);++i) 
#define FORR(i,a,b) for(i=(a);i>(b);--i)
#define REP(i,n) for(i=0;i<(n);++i)
#define REPR(i,n) for(i=(n);i>0;--i)
#define PB push_back
#define ull unsigned long long
#define ll long long
#define INT_MAX 2147483647
#define LL_MAX 9223372036854775807
#define sortR(a,b) sort(a, b, greater<int>())

using namespace std;

int main() {
	int N, M, T;
	cin >> N >> M >> T;
	if (N == M && M == T)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b)          for(i=a;i<b;i++)
#define repr(i,a,b)         for(i=a;i>=b;i--)

#define LL                  long long
#define ull                 unsigned long long int
#define scl(n)              scanf("%lld", &n)
#define scf(n)              scanf("%lf", &n)
#define sci(n)              scanf("%d", &n)
#define scii(n,m)           scanf("%d %d",&n,&m)
#define sciii(n,m,p)        scanf("%d %d %d",&n,&m,&p)
#define scs(n)              scanf("%s", n)
#define pfi(n)              printf("%d\n",n)
#define pfl(n)              printf("%I64d ",n)
#define pfs(s)              printf("%s\n",s)

#define MOD                 1000000007
#define MODP                99999999999973LL
#define pb                  push_back
#define ff                  first
#define ss                  second
#define mp                  make_pair
#define pp                  pair<int,int>
#define memo(a,b)           memset(a,b,sizeof(a))
#define INF                 1e9
#define EPS                 1e-8
#define Pi                  acos(-1.0)

#define N 100005


int main()
{

    int n;


    while(cin>>n && n)
    {

        LL arr[5000];

        for(int i=0;i<n;i++)
            scl(arr[i]);


        LL sum=0;
        LL res=LONG_LONG_MIN;


        for(int i=0;i<n;i++)
        {
            sum+=arr[i];
            
            res=max(res,arr[i]);
            res=max(res,sum);

            if(sum<=0)
                sum=0;
        }
       // cout<<"sss"<<endl;
       cout<<res<<endl;

    }

    return 0;
}

/* int dx[] = {1,-1,0,0} , dy[] = {0,0,1,-1}; */ // 4 Direction
/* int dx[] = {1,-1,0,0,1,1,-1,-1} , dy[] = {0,0,1,-1,1,-1,1,-1}; */ // 8 Direction
/* int dx[] = {1,-1,1,-1,2,2,-2,-2} , dy[] = {2,2,-2,-2,1,-1,1,-1}; */ // Knight Direction
/* int dx[] = {2,-2,1,1,-1,-1} , dy[] = {0,0,1,-1,1,-1}; */ // Hexagonal Direction



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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long int;
using ull = unsigned long long int;

int main() {
    int n;
    cin >> n;
    
    int ans = 0;
    for (int i = 1; i < n; ++i) {
        int remain = (n - 1) / i;
        ans += remain;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    const double PI = 3.14159265358979;
    IOS
    double a,b,x;
    cin >> a >> b >> x;
    x /= a;
    double ans = 0;
    if (x == a * b) ans = 0;
    else {
        if (x <= a * b / 2) {
            double a2 = x / b * 2;
            ans = atan2(b,a2);
            ans *= 180.0/PI;
        } else {
            // 台形の上底
            double b1 = x * 2 / a - b;
            b -= b1;
            x -= a * b1;
            ans = atan2(b,a);
            ans *= 180.0/PI;
        }
    }

    cout << fixed << setprecision(10) << ans << '\n';

    return 0;
}

Measured memory_bytes: 256
N = int(input())

board_size = 8
board = [[ '.' for _ in range(board_size)] for _ in range(board_size)]

def print_board(board):
    for bb in board:
        line = ""
        for b in bb:
            line = line + b
        print(line)

#print_board(board)

Q_list = list()
for _ in range(N):
 Q_list.append(tuple(map(int, input().split() )) )
#print(Q_list)

skip_raws = list()
for (r,c) in Q_list:
    board[r][c] = "Q"
    skip_raws.append(r)


def is_enable_put(r, c, board):
    ok = True
    
    for i in range(board_size):
        # horizontal search
        if board[r][i] == "Q" and i != c:
            ok = False
            break
        # vertical search
        if board[i][c] == "Q" and i != r:
            ok = False
            break
        #
        if i > 0:
            if r-i >= 0 and c-i >= 0 \
            and board[r-i][c-i] == "Q":
                ok = False
                break
            if i+r < board_size and i+c < board_size \
            and board[i+r][i+c] == "Q":
                ok = False
                break
            if r-i >= 0 and c+i < board_size \
            and board[r-i][c+i] == "Q":
                ok = False
                break
            if r+i < board_size and c-i >= 0 \
            and board[r+i][c-i] == "Q":
                ok = False
                break
    return ok

import copy
def queen(r, qboard):
    # print("---", r)
    # print_board(qboard)
    if r == board_size:
        print_board(qboard)
        return
    elif r in skip_raws:
        queen(r+1,qboard)
        return

    else:
        for c in range(board_size):
            if is_enable_put(r, c, qboard) == False: continue
            else:
                tmp_board = copy.deepcopy(qboard)
                tmp_board[r][c] = "Q"
                queen(r+1, tmp_board)

queen(0,board)



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

int main(){
  string s, t;
  cin >> s >> t;
  ll a, b;
  cin >> a >> b;
  string u;
  cin >> u;
  if(u == s) a--;
  if(u == t) b--;
  cout << a << " " << b << endl;
}


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

using namespace std;
typedef long long ll;
//typedef unsigned long long ll;

//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
//typedef pair<ll, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = LONG_LONG_MAX / 100;
//const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
//const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)

bool contain(set<char> &s, int a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
void print_line(vector<int> &line) {
    for (int i = 0; i < line.size(); i++) {
        cout << line[i];
        if (i == line.size() - 1) cout << endl;
        else cout << ' ';
    }
}

typedef priority_queue<long long, vector<long long>, greater<long long> > PQ_ASK;
const int mod = 1000000007;

bool is_prime(ll a) {
    for (int i = 2; i * i <= a; i++) {
        if (a % i == 0) return false;
    }
    return true;
}


int main() {
    int n;
    cin >> n;
    int count = 0;
    rep(i, n) {
        ll a;
        cin >> a;
        if (is_prime(a)) {
            count++;
        }
    }
    cout << count << endl;
}



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

using namespace std;

int main() {
    int W, H, N;

    cin >> W >> H >> N;

    vector<int> x(N), y(N), a(N);
    vector<int> A = {W, H};
    vector<int> B = {0, 0};

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

    for (int i = 0; i < N; i++) {
        switch(a.at(i)) {
            case 1:
                if (B.at(0) < x.at(i)) B.at(0) = x.at(i);
                break;
            case 2:
                if (A.at(0) > x.at(i)) A.at(0) = x.at(i);
                break;
            case 3:
                if (B.at(1) < y.at(i)) B.at(1) = y.at(i);
                break;
            case 4:
                if (A.at(1) > y.at(i)) A.at(1) = y.at(i);
                break;
            default:
                break;
        }
    }

    if ((A.at(0) - B.at(0) > 0) && (A.at(1) - B.at(1) > 0)) {
        cout << (A.at(0) - B.at(0)) * (A.at(1) - B.at(1)) << endl;
    } else {
        cout << 0 << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<queue>
using namespace std;
char map[55][55];
bool book[55][55];
int next_to[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
int n,m;
struct node
{
	int x,y,step;
};
queue<node>que;

int main()
{
	int i,j,x,y;
	int ans,cont;
	bool flag;
	while(~scanf("%d%d",&n,&m))
	{
		cont=0;
		flag=false;
		ans=m*n;
		memset(book,true,sizeof(book));
		for(i=0;i<n;i++)
		{
			scanf("%s",map[i]);
			for(j=0;j<m;j++)
			{
				if(map[i][j]=='#') 
				{
					book[i][j]=false;
					ans--;
				}
			}
		}
		node now;
		now.x=0;now.y=0;now.step=0;
		book[0][0]=false;
		que.push(now);
		int j=0;
		while(!que.empty())
		{
			//printf("%d\n",++j);
			now=que.front();
			for(i=0;i<4;i++)
			{
				x=now.x+next_to[i][0];
				y=now.y+next_to[i][1];
			//	printf("(%d,%d)\n",x,y);
				if(x<0 || y<0|| x>n || y>m) continue;
				if(book[x][y]==false) continue;
				if(x==n-1 && y==m-1)
				{
					flag=true;
					cont=now.step+2;
					break;
				}
				if(map[x][y]=='.')
				{
					node nextt;
					nextt.x=x;
					nextt.y=y;
					nextt.step=now.step+1;
					que.push(nextt);
					book[x][y]=false;
				}
			}
			if(flag) break;
			que.pop();
		}
		//printf("flag=%d\n",flag);
		if(flag)
			printf("%d\n",ans-cont);
		else 
			printf("-1\n");
		while(!que.empty())
		{
			que.pop();
		}
	
	}
	return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
using Graph = vector<vector<int>>;
using Graphl = vector<vector<ll>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Rep(i, k, n) for (int i = k; i < (int)(n); i++)
#define RRep(i, k, n) for (int i = k; i > (int)(n); i--)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define ALL(a)  (a).begin(),(a).end()
#define rALL(a)  (a).rbegin(),(a).rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> void PrintVector(const vector<T> &vec) {for (auto val : vec) cout << val << " "; cout << endl;}
const long long INF = 1LL << 60;
const long long minusINF = -(1LL << 40);
const int MOD = 1000000007;
const double PI = acos(-1); //3.14~
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main()
{
    int n, m, X, Y; cin >> n >> m >> X >> Y;
    vector<int> x(n), y(m);
    rep(i, n) cin >> x[i];
    rep(i, m) cin >> y[i];

    sort(rALL(x));
    sort(ALL(y));
    int maxx = x[0];
    int miny = y[0];

    Rep(i, maxx + 1, miny + 1)
    {
        if (i > X && i <= Y)
        {
            cout << "No War" << endl;
            return 0;
        }
    }
    cout << "War" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue>
using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef pair<int, int> P;
const int c_INF = 111111111;
const int c_mINF = -111111111;
const int c_YET = -1;
const int c_Dx[4] = { 0,0,1,-1 };
const int c_Dy[4] = { 1,-1,0,0 };


int main() {
	int N;
	int H[30];
	scanf("%d", &N);
	for (int i = 0; i < N; i++)scanf("%d", &H[i]);

	int count = N;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < i; j++)
			if (H[i] < H[j]) {
				count--;
				break;
			}


	printf("%d", count);



}

/*         提出前の確認事項

・デバッグ用の関数は＜＜コメント化＞＞しているか？
・すべての＜＜入力例＞＞は試したか？
・＜＜限界値分析＞＞はしたか？
・＜＜出力の改行＞＞の有無は確認したか？
・文字列の＜＜スペル＞＞は確認したか？
　　　　　　　　↓
	 ＜＜提出先＞＞に注意して提出！！
*/

Measured memory_bytes: 128
import java.util.*;
public class Main{
    static Scanner kbd = new Scanner(System.in);
    public static void main(String[] args){
	while(kbd.hasNext()){
	    int n = kbd.nextInt();  // テァツォツカテヲツ環?ィツ??」ツ?ョテ、ツコツコテヲツ閉ー
	    int m = kbd.nextInt();  // テ・ツ仰敕」ツ?」テ」ツ?淌、ツコツコテ」ツ?ョテァツ閉ェテ・ツ渉キ 
	    double p = kbd.nextInt();  // テヲツ篠ァテゥツ卍、テァツ篠?
	    if(!(n==0 && m==0 && p==0)){
		
		int[] a = new int[n];   // nテァツ閉ェテァツ崢ョテ」ツ?ョテ、ツコツコテ」ツ?ォティツウツュテ」ツ?妥」ツ?淌、ツコツコテヲツ閉ーテ」ツつ津、ツソツ敕・ツュツ?
		int i;
		int  money = 0;
		for(i=0; i<n; i++){
		    a[i] = kbd.nextInt();
		    money += a[i]*100;
		}
		// テ「ツ?僧oney = ティツウツュテ」ツ?妥ゥツ?妥」ツ?ョテァツキツ湘ゥツ。ツ?

		money -= money*(p/100);
		// テ「ツ?僧oney = テ・ツ渉療」ツ?妥・ツ渉姪」ツつ古」ツつ凝ヲツ慊?・ツ、ツァテゥツ?妥ゥツ。ツ?

		if(a[m-1]==0){
		    System.out.println("0");
		    // テ「ツ?妥ィツウツュテ」ツ?妥」ツ?淌、ツコツコテ」ツ?古・ツアツ?」ツ?ェテ」ツ?妥」ツつ古」ツ?ーテ・ツ渉療」ツ?妥・ツ渉姪」ツつ古」ツ?ェテ」ツ??
		}
		else {
		    money = money/a[m-1];
		    // テ「ツ?僧oney = テ、ツクツ?、ツコツコテ・ツスツ禿」ツ?淌」ツつ甘」ツ?ョテゥツ?催・ツスツ禿ゥツ??
		    System.out.println(money);
		}
	    }
	}
    }
}

Measured memory_bytes: 27644
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

# nCr mod m
# modinvが必要
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10 ** 9 + 7):
    r = min(r, n - r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i + 1, mod) % mod
    return res

x,y = map(int, input().split())
b = (2*y - x) / 3
a = (2*x - y) / 3
if not b.is_integer() or not a.is_integer() or a < 0 or b < 0:
    print(0)
else:
    print(combination(int(a+b), int(a)))


Measured memory_bytes: 90584
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio>
#include<stdio.h>
#include<cmath>
#include<math.h>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<sstream>
#define forn(i,n) for(int (i)=0;i<(n);i++)
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int>pii;
typedef long long ll;
typedef pair<ll,ll> pll;
const int MAXN=100005;
const int INF=2147483647;
const ll LINF=9223372036854775807;
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int n;
void dfs(char mx,string s)
{
	if(s.size()==n)
	{
		cout<<s<<endl;
		return;
	}
	for(char c='a';c<=mx;c++)
	{
		s+=c;
		dfs(mx,s);
		s=s.substr(0,s.size()-1);
	}
	s+=(mx+1);
	dfs(mx+1,s);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	dfs('a',"a");
	return 0;
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
#define sz 1000009
#define mx 10000000000008
#define mod 1000000007
ll n,t,arr[sz],brr[sz],crr[sz],j;
vector<ll>v;
char c[sz];
int main()
{
    for(int i=1;i<=1000000;i++)
    {
        for(int j=i;j<=1000000;j+=i)
            arr[j]++;
    }
    for(int i=1;i<=1000000;i++)
        arr[i]+=arr[i-1];
    scanf("%lld",&n);
    printf("%lld\n",arr[n-1]);
    return 0;
}


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

using namespace std;

const int MOD = 1e9 + 7;

int a[100005];
long long fact[100005], inv[100005];

long long my_pow(long long a, int lv) {
	long long res = 1;
	long long p = a;
	while (lv) {
		if (lv & 1) res = res * p % MOD;
		p = p * p % MOD;
		lv >>= 1; 
	}
	return res;
}

long long ncr(int n, int r) {
	return fact[n] * inv[r] % MOD * inv[n - r] % MOD;
}

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	
	sort(a, a + n);
	
	fact[0] = 1LL;
	for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
	inv[n] = my_pow(fact[n], MOD - 2);
	for (int i = n - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
	
	long long mx = 0;
	long long mn = 0;
	
	for (int i = k - 1; i < n; i++) {
		mx = (mx + ncr(i, k - 1) * a[i]) % MOD;
	}
	
	for (int i = n - k; i >= 0; i--) {
		mn = (mn + ncr(n - 1 - i, k - 1) * a[i]) % MOD;
	}
	
	printf("%lld\n", (mx - mn + MOD) % MOD);
}


Measured memory_bytes: 5640
#include<bits/stdc++.h>
#define maxn 505
using namespace std;
typedef long long ll;
int a[maxn][maxn];
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    while (m--){
        int l, r;
        cin >> l >> r;
        ++a[l][r];
    }
    for (int i = n; i >= 1; --i){
        for (int j = 1; j <= n; ++j){
            a[i][j] += a[i + 1][j] + a[i][j - 1] - a[i + 1][j - 1];
        }
    }
    while (q--){
        int l, r;
        cin >> l >> r;
        cout << a[l][r] << '\n';
    }
    return 0;
}


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

const int D = 4;
const int MODN = 1e9 + 7;

struct M {
	int d[D][D];
	M() {
		memset(d, 0, sizeof d);
	}
	M operator*(const M& other) const {
		M ret;
		for (int j = 0; j < D; ++ j)
			for (int i = 0; i < D; ++ i)
				for (int k = 0; k < D; ++ k) {
					ret.d[i][k] = (1LL * d[i][j] * other.d[j][k] + ret.d[i][k]) % MODN;
				}
		return ret;
	}
};

M pw(M x, int n) {
	M ret;
	for (int i = 0; i < D; ++ i) ret.d[i][i] = 1;
	for (; n; n >>= 1, x = x * x)
		if (n & 1) ret = ret * x;
	return ret;
}

int main() {
	std::ios::sync_with_stdio(false);
	M T, cur, Tb;
	for (int i = 0; i < D; ++ i) cur.d[i][i] = 1;
	T.d[0][3] = 1;
	T.d[1][1] = T.d[1][3] = 1;
	T.d[2][1] = T.d[2][2] = T.d[2][3] = 1;
	T.d[3][1] = 1; T.d[3][2] = T.d[3][3] = 2;

	Tb.d[1][1] = 1;
	Tb.d[2][1] = Tb.d[2][2] = 1;
	Tb.d[3][1] = 1; Tb.d[3][2] = 2; Tb.d[3][3] = 1;

	int n, m; std::cin >> n >> m;
	int last = 0;
	for (int i = 0; i < m; ++ i) {
		int x; std::cin >> x;
		cur = pw(T, x - last - 1) * cur;
		cur = Tb * cur;
		last = x;
	}

	cur = pw(T, n - last) * cur;
	int ans = 0;
	for (int i = 0; i < D; ++ i)
		ans = (ans + cur.d[0][i]) % MODN;
	std::cout << ans << std::endl;
}

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

#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

using namespace std;

typedef long long LL;

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vec) {
    os << "[ ";
    REP(i, vec.size()) {
        os << vec[i] << " ";
    }
    os << "]";

    return os;
}

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

    LL N;
    cin >> N;

    LL ret = 0;
    FOR(i, 1, N) {
        ret += i;
    }

    cout << ret << endl;

}


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

namespace {
void solve() {
  int32_t n;
  std::cin >> n;

  int32_t a = 0;
  std::vector<int32_t> v(n, 0), c(n, 0);
  for (int32_t i = 0; i < n; i++) {
    std::cin >> v[i];
  }
  for (int32_t i = 0; i < n; i++) {
    std::cin >> c[i];
    v[i] -= c[i];
    if (v[i] > 0) {
      a += v[i];
    }
  }

  std::cout << a << std::endl;
}
} // namespace

int32_t main(void) { solve(); }


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

Measured memory_bytes: 604
def inpl():
    return list(map(int, input().split()))


N, M = inpl()
AB = [inpl() for _ in range(N)]

AB.sort()
ans = 0
i = 0
while M != 0:
    ans += min(M, AB[i][1]) * AB[i][0]
    M -= min(M, AB[i][1])
    i += 1
print(ans)


Measured memory_bytes: 27876
/**********************************************************************/
/********                                                      ********/
/********                     Writer:孙~~                      ********/
/********                       Lang:C++                       ********/
/********                     Status:Unknow                    ********/
/********                                                      ********/
/**********************************************************************/
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <list>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <cstring>
#include <cmath>
//#include<bits/stdc++.h>
using namespace std;

const int INF=0x3f3f3f3f;
const int SIZE=1005;
const double EPS=1e-6;
const int MOD=1e9+7;

int dp[SIZE][SIZE];
char s[SIZE][SIZE];

int main(){
	/*main function start*/
	int h,w;
	scanf("%d%d",&h,&w);
	for(int i=0;i<h;i++){
		scanf("%s",s[i]);
	}
	dp[0][1]=1;
	for(int i=1;i<=h;i++) for(int j=1;j<=w;j++){
		if(s[i-1][j-1]=='#') dp[i][j]=0;
		else{
			dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD;
		}
	}
	printf("%d\n",dp[h][w]);
	return 0;
}


Measured memory_bytes: 5120
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<ll, int> Pl;
typedef pair<int, pair<int, int>> PP;
typedef pair<P, int> PPi;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1e+9 + 7;
// constexpr int mod = 998244353;

int n, m;
vector<vector<int>> graph;

vector<double> dp(605, -1);
vector<double> dp2;

double memo_rec(int u){
    if(dp[u] != -1) return dp[u];
    if(u == n - 1)  return dp[u] = 0;

    double res = 0;
    for(int v : graph[u])   res += memo_rec(v);
    res /= graph[u].size();
    res += 1;
    return dp[u] = res;
}

double memo_rec2(int u, const int &from, const int &to){
    if(dp2[u] != -1)    return dp2[u];
    if(u == n - 1)  return dp2[u] = 0;

    double res = 0;
    int cnt = 0;
    for(int v : graph[u]){
        if(u == from && v == to)    continue;
        res += memo_rec2(v, from, to);
        ++cnt;
    }
    res /= cnt;
    res += 1;
    return dp2[u] = res;
}

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

    cin >> n >> m;
    graph.resize(n);
    for(int i = 0; i < m; ++i){
        int s, t;
        cin >> s >> t;
        --s, --t;
        graph[s].push_back(t);
    }
    
    double ans = memo_rec(0);
    dp2.resize(n);
    for(int u = 0; u < n - 1; ++u){
        if(graph[u].size() == 1)    continue;

        for(int i = 0; i < n; ++i)  dp2[i] = -1;
        int from = u, to = graph[u][0];
        for(int v : graph[u]){
            if(v == to) continue;
            if(dp[v] > dp[to])  to = v;
        }
        double foo = memo_rec2(0, from, to);
        chmin(ans, foo);
    }
    cout << fixed << setprecision(10);
    cout << ans << endl;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
 ll n,W;
 cin>>n>>W;
 vector<ll> w(n),v(n);
 ll V=0;
 for(ll i=0;i<n;i++){cin>>w[i]>>v[i];V+=v[i];}
 vector<vector<ll>> dp(n,vector<ll>(V+1));
 ll INF=1e9+7;
 for(ll i=0;i<=V;i++) dp[n-1][i]=INF;
 dp[n-1][v[n-1]]=w[n-1];
dp[n-1][0]=0;
 for(ll i=n-2;i>=0;i--){
  for(ll j=0;j<=V;j++){
   if(j<v[i]) dp[i][j]=dp[i+1][j];
   else dp[i][j]=min(dp[i+1][j],dp[i+1][j-v[i]]+w[i]);
  }
 }
// cout<<"|| Solution ||"<<endl;
 for(ll i=V;i>=0;i--){
  if(dp[0][i]<=W){
   cout<<i<<endl;
   return 0;
  }
 }
 cout<<endl;
 return 0;
}

Measured memory_bytes: 79488
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Collections;
import java.util.Scanner;
import java.util.TreeSet;

public class Main{
       
	public static void main(String[] args) {
		Scanner sdf = new Scanner(System.in);
		
                int t=1;
                while(t-->0){
                    int n=sdf.nextInt();
                    int k=sdf.nextInt();
                    if(n>1){
                    System.out.println((int)Math.ceil(Math.log(n)/Math.log(k)));
                    }
                    else System.out.println("1");
                    
                
                }                
        }
   


}

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

using namespace std;

typedef long long ll;

const ll M = 1e9+7;

ll x, y, ans;
ll fact[2200000];

ll mpow(ll a, ll n)
{
  if (n == 0) return 1;
  if (n % 2) return mpow(a, n-1) * a % M;
  return mpow(a * a % M, n/2);
}

ll cmb(ll n, ll r)
{
  return fact[n] * mpow(fact[r], M-2) % M * mpow(fact[n-r], M-2) % M;
}

int main()
{
  cin >> x >> y;
  
  fact[0] = 1;
  for (int i = 1; i <= 2100000; ++i) {
    fact[i] = fact[i-1] * i % M;
  }

  ll n = x + y;
  
  if (n % 3 or x * 2 < y or y * 2 < x) {
    cout << 0 << endl;
    return 0;
  }
  
  x -= n/3;
  y -= n/3;
  
  ans = cmb(x+y, x);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 16640
#include<cstdio>
int main(){
    int m,k;
    scanf("%d%d",&m,&k);
    int max_num = 1<<m;
    if(max_num<=k || (m==1&&k==1)){
        printf("-1\n");
        return 0;
    }else if(k==0){
        for(int i=0;i<max_num;i++){
            printf("%s%d %d",(i==0)?"":" ",i,i);
        }
        printf("\n");
    }else{
        for(int i=0;i<max_num;i++){
            if(i!=k){
                printf("%d ",i);
            }
        }
        printf("%d",k);
        for(int i=max_num-1;i>=0;i--){
            if(i!=k){
                printf(" %d",i);
            }
        }
        printf(" %d\n",k);
    }
    return 0;
}

Measured memory_bytes: 1792
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    ll X[110];
    rep(i,0,N) cin >> X[i];
    ll ans = INF;
    rep(p,0,101){
        ll res = 0;
        rep(i,0,N){
            res += (p - X[i]) * (p - X[i]);
        }
        ans = min(ans, res);

    }
    print(ans);


    

}

Measured memory_bytes: 256
N = gets.to_i
JOB = Array.new(N){gets.split.map &:to_i}
JOB.sort_by!{|v|v[1]}.reverse!

t = 10**9+7

JOB.each do |(a,b)|
  t = b if b < t
  t -= a
  if t < 0
    puts "No"
    exit
  end
end
puts "Yes"

Measured memory_bytes: 23056
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <vector>
#include <stack>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <unordered_map>


using namespace std;

typedef long long ll;

const int maxn=2e5+10;
int main()
{
  map<ll,int> s;
  int n,m;
  ll d[maxn],t[maxn];
  scanf("%d",&n);
  for(int i=0;i<n;i++)
  {
    scanf("%lld",&d[i]);
    s[d[i]]++;
  }
  scanf("%d",&m);
  for(int i=0;i<m;i++)
  {
    scanf("%lld",&t[i]);
    if(s.find(t[i])==s.end())
    {
      cout<<"NO";
      return 0;
    }
    s[t[i]]--;
    if(s[t[i]]==0)
      s.erase(t[i]);
  }
  cout<<"YES";
  
  return 0;
}

Measured memory_bytes: 15872
A,B,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
x = [0 for _ in range(m)]
y = [0 for _ in range(m)]
c = [0 for _ in range(m)]
for i in range(m):
    x[i],y[i],c[i] = map(int,input().split())

ans = min(a)+min(b)

for i in range(m):
    ans = min(ans,(a[x[i]-1] + b[y[i]-1]) - c[i])
print(ans)

Measured memory_bytes: 23396
N, T = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(N)]
lst = []
lst2 = []

for i in range(N):
    lst.append(x[i][1])

if min(lst) <= T:
    for i in range(N):
        if x[i][1] <= T:
            lst2.append(x[i][0])

    print(min(lst2))

else:
    print('TLE')

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  for(int i=0;i<19;i++){
    if(i==5 || i==13){
      cout<<" ";
    }
    else cout<<s[i];
  }
  cout<<endl;
  return 0;
}

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

using namespace std;

#define ll long long

int main(){
    ll N, M, C;
    ll tmp = 0, b = 0;
    ll ans = 0;
    cin >> N >> M >> C;
    vector<ll> B(M);
    int A[22][22];
    for(int i = 0; i < M; i++){
        cin >> B[i];
    }
    for(int i = 0; i < N; i++){
        tmp = C;
        for(int j = 0; j < M; j++){
            cin >> A[i][j];
            tmp += B[j] * A[i][j];
        }
        if(tmp > 0)ans++;
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 888
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
a = sum(A) ** 2 % mod
b = sum([a * a for a in A]) % mod
p = mod - 2
bin_p = []
while p:
  bin_p.append(p % 2)
  p >>= 1
ret = 1
for j in reversed(bin_p):
  ret = (ret * ret) % mod
  if j == 1:
    ret = (ret * 2) % mod
print((a - b) * ret % mod)

Measured memory_bytes: 101952