akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <map>
#include <iomanip>
#include <limits>
#define rep(i, n) for(int i = 0; i < n; i++)
typedef long long ll;
using namespace std;

int asc(const void* a, const void* b) {
	return *(int*)a- *(int*)b;
}

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

//素因数分解
vector<pair<ll, int>> factorize(ll n) {
	vector<pair<ll, int>> res;
	for (ll i = 2; i * i <= n; i++) {
		if (n % i) continue;
		res.emplace_back(i, 0);
		while (n % i == 0) {
			n /= i;
			res.back().second++;
		}
	}
	if (n != 1) res.emplace_back(n, 1);
	return res;
}

int main()
{
	int n, d[105], ans = 0;
	cin >> n;
	rep(i, n) cin >> d[i];
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			ans += d[i] * d[j];
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
/* #include <regex> */

using namespace std;

/* g++ -g -std=c++11 */

/* freopen("input.txt", "rt", stdin); */
/* freopen("output.txt", "wt", stdout); */

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }


int main()
{
#ifdef foo_
    freopen("foo", "rt", stdin);
#endif
    ios::sync_with_stdio(false);
    int n,k;
    while (cin >> n >> k) {
        string s; cin >> s;
        map<int,int> ones; vector<PII> zeros;
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') {
                const int lft = i;
                while (i+1 < n && s[i+1] == '0')
                    i++;
                const int rht = i+1;
                zeros.push_back({lft,rht});
            }
            else {
                const int lft = i;
                while (i+1 < n && s[i+1] == '1')
                    i++;
                const int rht = i+1;
                ones[lft] = rht-lft;
            }
        }
        if (zeros.size() <= k)
            cout << n << endl;
        else {
            int i = 0, j = i+k-1, ans = 0;
            while (j < zeros.size()) {
                const int lft = zeros[i].first;
                const int rht = zeros[j].second;
                int best = rht-lft + ones[rht];
                if (i == 0)
                    best += lft;
                else
                    best += ones[zeros[i-1].second];
                ans = max(ans,best);
                i++, j++;
            }
            cout << ans << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3144
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N];
int b[N];
int main()
{
    int n,m,k,A,B,x,mna = 1e9,mnb = 1e9,mn = 1e9;
    scanf("%d %d %d",&n,&m,&k);
    for(int i=1;i<=n;i++)   scanf("%d",&a[i]),mna = min(mna,a[i]);
    for(int i=1;i<=m;i++)   scanf("%d",&b[i]),mnb = min(mnb,b[i]);
    for(int i=1;i<=k;i++)   scanf("%d %d %d",&A,&B,&x),mn = min(mn,a[A]+b[B]-x);
    printf("%d\n",min(mna+mnb,mn));
}


Measured memory_bytes: 1024
#include<iostream>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include <algorithm> 
using namespace std;

# define p(s) std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;



int main()
{
    int h,w;cin >> h >> w;

    char s[50][50];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin >> s[i][j];
        }
    }

    bool flg=true;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j]=='#'){
                bool t1=true;
                bool t2=true;
                bool t3=true;
                bool t4=true;
                if(i-1>=0)   if(s[i-1][j]=='#') t1=false;
                if(i+1<=h-1) if(s[i+1][j]=='#') t2=false;
                if(j-1>=0)   if(s[i][j-1]=='#') t3=false;
                if(j+1<=w-1) if(s[i][j+1]=='#') t4=false;
                if(t1 && t2 && t3 && t4) {
                    flg=false;
                }
            }
        }
    }
    Yes(flg)
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool box[17000000]={false};
void change(string t);
int n;
string s,t,r;
int sum;
int main(void){
	
	int i;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>s>>t;
		sum=0;
		if(s=="insert"){
			change(t);
			//cout<<"sum="<<sum<<endl;
			box[sum]=true;
		}
		else{	
			change(t);
			//cout<<"sum="<<sum<<endl;
			cout<<((box[sum])?"yes":"no")<<endl;
		}
	}
	return 0;
}
void change(string t){
	int i;
	r="";
	for(i=t.size()-1;i>=0;i--){
		r.push_back(t[i]);
	}
	for(i=0;i<r.size();i++){
		if(r[i]=='A'){
			sum+=1*pow(4,i);
		}
		else if(r[i]=='C'){
			sum+=2*pow(4,i);
		}
		else if(r[i]=='G'){
			sum+=3*pow(4,i);
		}
		else{
			sum+=4*pow(4,i);
		}
	}
}
		
	
	


Measured memory_bytes: 4688
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f;

int a[100005],b[100005],c[100005],dp[100005][3];

signed main()
{
	int n;
	while(cin>>n){
		for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i]>>c[i];
		
		dp[1][0]=a[1],dp[1][1]=b[1],dp[1][2]=c[1];
		for(int i=2;i<=n;i++){
			dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
			dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
			dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i]; 
		}
		
		int ans=0;
		for(int i=0;i<=2;i++)
		ans=max(ans,dp[n][i]);
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 5960
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l long
#define pb push_back
#define mp make_pair
#define mt make_tuple

int main() {
	// your code goes here
	//ifstream cin("input.txt");
	//ofstream cout("output.txt");
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
	
	int n; cin>>n;
	cout<<fixed<<setprecision(10);
	double ans;
	double a[n];
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n);
	ans = a[0];
	for(int i=1;i<n;i++)
	{
	    ans = (ans + a[i])/2.0;
	}
	
	cout<<ans;
	
	
	return 0;
}


Measured memory_bytes: 256
n=int(input())
l=list(map(int, input().split()))
a=0
for i in range(n):
  for j in range(i+1, n):
    for k in range(j+1, n):
      tot = l[i]+l[j]+l[k]
      maxl = max(l[i],l[j],l[k])
      if l[i]!=l[j] and l[i]!=l[k] and l[j]!=l[k] and tot>2*maxl:
        a+=1
print(a)

Measured memory_bytes: 9204
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007LL;
const int INF = LLONG_MAX;

signed main(){
    
    int n; cin >> n;
    int ans = 1;
    for(int i = 1; i <= n; i++){
        ans *= i;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}

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

void Main()
{
    int64_t N;
    cin >> N;

    int64_t result = 0;
    for(int64_t i = 0; i <= N; ++i)
    {
        if(i % 3 != 0 && i % 5 != 0)
        {
            result += i;
        }
    }

    cout << result << endl;
}

int main()
{
    Main();
}


Measured memory_bytes: 3620
// Problem : D - Chat in a Circle
// Contest : AtCoder - AtCoder Beginner Contest 173
// URL : https://atcoder.jp/contests/abc173/tasks/abc173_d
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define eb emplace_back
#define pb push_back
#define size(s) (int)s.size()
#define int long long
#define vi vector<int>
#define vs vector<string>
#define vv vector<vector<int>>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define f first
#define se second
#define inc(v,n,x) v.assign(n,x)
#define incd(v,n) v.resize(n)
#define iniz(n) memset(n,0,sizeof(n))
#define inin(n) memset(n,-1,sizeof(n))
#define inimi(n) memset(n,0xc0,sizeof(n))
#define inima(n) memset(n,0x3f,sizeof(n))
#define all(v) (v).begin(),(v).end()

using namespace std;

template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

const int N=200001;
double pi=acos(-1.0);
int md=1e9+7;
const int INF=1e15;
int dx1[]={0,0,-1,1};
int dy1[]={1,-1,0,0};

template<class T>
T abst(T a)
{return a<0?-a:a;}

template<class T>
T max2(T a,T b){return a>b?a:b;}
template<class T>
T min2(T a,T b){return a<b?a:b;}

void solve()
{
	int n;cin>>n;
	vi v(n);cin>>v;
	sort(all(v),greater<int>());
	int ans=v[0];
	int ptr=1,cnt=0;
	for(int i=3;i<=n;i++)
	{
		if(cnt==2)
		{
			cnt=1;
			ptr++;
			ans+=v[ptr];
		}
		else
		{
			cnt++;
			ans+=v[ptr];
		}
	}
	cout<<ans;
}

int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)
{
    solve();
}
return 0;
}


Measured memory_bytes: 4780
import sys
def main():
    H1, M1, H2, M2, K = map(int, input().split())
    
    h = H2 - H1 
    m = M2 - M1
    tot_minutes = h * 60 + m - K
    
    if tot_minutes <= 0:
        out = 0
    else:
        out = tot_minutes
    print(out)
main()

Measured memory_bytes: 9164
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
int main()
{
  int a[3];
  cin >> a[0] >> a[1] >> a[2];
  sort(a, a + 3);
  cout << a[0] * a[1] / 2 << endl;
  return 0;
}


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

using namespace std;

bool i_empty(const array<int, 3> &d) {
  return d[0] == 0 && d[1] == 0 && d[2] == 0;
}

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

  int n, y;
  cin >> n >> y;
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= n - i; ++j) {
      int sen = n - i - j;
      int money = i * 10000 + j * 5000 + sen * 1000;
      if (money == y) {
        cout << i << " " << j << " " << sen << "\n";
        return 0;
      }
    }
  }
  cout << "-1 -1 -1\n";
}


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

struct TCard{
	int Number;
	char Mark;
    bool operator<(const TCard &Y) const;
    bool operator==(const TCard &Y) const;	
};

bool TCard::operator<(const TCard &Y) const
{
	return Number < Y.Number;
}

bool TCard::operator==(const TCard &Y) const
{
	return Number == Y.Number;
}

int Partition(vector<TCard>& A, int p, int r)
{
	int i = p-1;
	for(int j = p; j < r; j++){
		if(A[j].Number <= A[r].Number){
			i++;
			swap(A[i], A[j]);
		}
	}
	swap(A[i+1], A[r]);
	return i+1;
}

void QuickSort(vector<TCard>& A, int p, int r){
	if(p < r){
		int q = Partition(A, p, r);
		QuickSort(A, p, q-1);
		QuickSort(A, q+1, r);
	}
}

bool IsStable(const vector<TCard>& A, const vector<TCard>& B)
{
	for(int i = 0; i < A.size(); i++){
		if(A[i].Mark != B[i].Mark){
		    return false; 
		}
	}
	return true;
}

int main()
{
	int n;
	cin >> n;
	vector<TCard> A(n);
	for(int i = 0; i < n; i++){
		cin >> A[i].Mark >> A[i].Number;
	}
	vector<TCard> B = A;
	std::stable_sort(B.begin(), B.end());
	QuickSort(A, 0, n-1);
	if(IsStable(A, B)){
		cout << "Stable" << endl;
	}else{
		cout << "Not stable" << endl;
	}
	for(int i = 0; i < n; i++){
		cout << A[i].Mark << ' ' << A[i].Number << endl;
	}
	return 0;
}

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

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a.at(i);
    }
    sort(a.begin(), a.end());
    vector<int> b(n+10);
    ll count=0;
    for (int i = 0; i < n; i++)
    {
        if (a.at(i) <= n)
        {
            b.at(a.at(i))++;
        }
        else{
            count++;
        }
    }
    
    for(int i=0;i<=n;i++){
        if(b.at(i)<i){
            count+=b.at(i);
        }
        if(b.at(i)>i){
            count+=b.at(i)-i;
        }
    }
    cout<<count<<endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
  int N,K;
  cin>>N>>K;
  vector<int> A(N);
  for(int &i:A)cin>>i;
  sort(A.begin(),A.end());
  int ans=10000000000;
  for(int i=0;i+K-1<N;i++)ans=min(ans,A[i+K-1]-A[i]);
  cout<<ans<<endl;
}

Measured memory_bytes: 3988
N = int(input())
H = [int(x) for x in input().rstrip().split(' ')]
max_cnt = 0
now_cnt = 0

for i in range(len(H)-1):
  if H[i] >= H[i+1]:
    now_cnt += 1
  else:
    now_cnt = 0
  if now_cnt >= max_cnt:
      max_cnt = now_cnt

print(max_cnt)

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


vector<vector<int> > g,rg;



int done1[1010];
int done2[1010];
int numb[1010];
vector<int> tpr;
int dfs(int x){
	if( done1[x]++ ) return 0;
	for(int i = 0 ; i < g[x].size() ; i++)
		dfs(g[x][i]);
	tpr.push_back(x);
}
int rdfs(int x,int k){
	if( done2[x]++ ) return 0;
	for(int i = 0 ; i < rg[x].size() ; i++)
		rdfs(rg[x][i],k);
	numb[x] = k;
}

int field[1010][1010];
int in[1010];

vector<vector<int> >  newg;
int scc(){
	for(int i = 0 ; i < g.size() ; i++){
		dfs(i);
	}
	reverse(tpr.begin(),tpr.end());
	int cnt = 0;
	for(int i = 0 ; i < tpr.size() ; i++){
		int x = tpr[i];
		if( done2[x] == 0 ){
			rdfs(x,cnt++);
		}
	}
	int n = tpr.size();
	
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < g[i].size() ; j++){
			int to = g[i][j];
			field[numb[i]][numb[to]] = true; 
		}
	}
	newg.resize(cnt);
	for(int i = 0 ; i < cnt ; i++){
		for(int j = 0 ; j < cnt ; j++){
			if( i != j && field[i][j] ) newg[i].push_back(j) , in[j]++;
			
		}
	}
	return -1;
}
#define MOD (1000000007)

long long memdfs(int x){
	long long ans = 1;
	for(int i = 0 ; i < newg[x].size() ; i++){
		ans *= memdfs(newg[x][i]);
		ans %= MOD;
	}
	return (ans + 1)%MOD;
}

int main(){
	int N,M;
	cin >> N >> M;
	g.resize(N);
	rg.resize(N);
	for(int i = 0 ; i < M ; i++){
		int a,b;
		cin >> a >> b;
		a--,b--;
		g[b].push_back(a);
		rg[a].push_back(b);
	}
	scc();
	long long ans = 1;
	for(int i = 0 ; i < newg.size() ; i++){
		if( in[i] == 0 ){
			ans *= memdfs(i);
			ans %= 1000000007;
		}
	}
	cout << ans % MOD << endl;
}

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


int main(){
    int A,B;
    cin >> A >> B;
    if(A <= 5){
        cout << 0;
    }else if(6 <= A and A <= 12){
        cout << B/2;
    }else if(13 <= A){
        cout << B;
    }
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define INFTY 1000000000

void quickSort( char *, int *, int, int );
int partition( char *, int *, int, int );
void merge( char *, int *, int, int, int );
void mergeSort( char *, int *, int, int );

int main()
{
  int i, n, *A, *B;
  char *M, *MM;
    
  scanf("%d", &n);
  A = malloc( n * sizeof(int));
  M = malloc( n * sizeof(char));
  B = malloc( n * sizeof(int));
  MM = malloc( n * sizeof(char));
  for( i=0; i<n; i++ )
    {
      scanf("%*c%c%d", &M[i], &A[i]);
      MM[i] = M[i];
      B[i] = A[i];
    }
  
  quickSort( M, A, 0, n-1 );
  mergeSort( MM, B, 0, n );

  if( strcmp(M,MM)==0 ) printf("Stable\n");
  else printf("Not stable\n");
  
  for( i=0; i<n; i++ ) printf("%c %d\n", M[i], A[i]);

  return 0;
}



void quickSort( char *M, int *A, int p, int r )
{
  int q;

  if( p < r )
    {
      q = partition( M, A, p, r );
      quickSort( M, A, p, q-1 );
      quickSort( M, A, q+1, r );
    }
}


int partition( char *M, int *A, int p, int r )
{
  int i, j, x, temp1;
  char temp2;

  x = A[r];
  i = p-1;

  for( j=p; j<r; j++ )
    {
      if( A[j] <= x )
	{
	  i = i + 1;
	  temp1 = A[i];
	  A[i] = A[j];
	  A[j] = temp1;

	  temp2 = M[i];
	  M[i] = M[j];
	  M[j] = temp2;
	  
	}
    }

  temp1 = A[i+1];
  A[i+1] = A[r];
  A[r] = temp1;

  temp2 = M[i+1];
  M[i+1] = M[r];
  M[r] = temp2;

  return i+1;
}

 
void merge( char *MM, int *B, int left, int mid, int right )
{
  int i, j, k, n1, n2, *L, *R;
  char *LM, *RM;
  
  
  n1 = mid - left;
  n2 = right - mid;

  L = malloc( (n1+1) * sizeof(int));
  R = malloc( (n2+1) * sizeof(int));
  LM = malloc( (n1+1) * sizeof(char));
  RM = malloc( (n2+1) * sizeof(char));
  
  for( i=0; i<n1; i++ )
    {
      L[i] = B[left + i];
      LM[i] = MM[left + i];
    }
  
  for( i=0; i<n2; i++ )
    {
      R[i] = B[mid + i];
      RM[i] = MM[mid + i];
    }
  
  L[n1] = INFTY; 
  R[n2] = INFTY;
  i = 0;
  j = 0;
    
  for( k=left; k<right; k++ )
    {
      if( L[i] <= R[j] )
	{
	  B[k] = L[i];
	  MM[k] = LM[i];
	  i = i + 1;
	}
      else
	{
	  B[k] = R[j];
	  MM[k] = RM[j];
	  j = j + 1;
	}
    }
}

      
void mergeSort( char *MM, int *B, int left, int right )
{
  int mid;
  
  if( left+1 < right )
    {
      mid = (left + right)/2;
      mergeSort(MM, B, left, mid);
      mergeSort(MM, B, mid, right);
      merge(MM, B, left, mid, right);
    }

}



Measured memory_bytes: 21352
import math
a, b, c = map(int, input().split())
s = (a*b*math.sin(math.radians(c)))/2
d = math.sqrt(a**2 + b**2 - 2*a*b*math.cos(math.radians(c)))
l = a + b + d
h = (2*s)/a
print(s)
print(l)
print(h)


Measured memory_bytes: 5704
#include <iostream>

int main(int argc, char *argv[]) {
  int a, b;
  std::cin >> a >> b;
  if (a < b)
    for (int i = 0; i < b; ++i)
      std::cout << a;
  else
    for (int i = 0; i < a; ++i)
      std::cout << b;
}


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

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int MOD = 1e9 + 7;

int add(int x, int y) {
  x += y;
  if (x >= MOD) {
    x -= MOD;
  }
  return x;
}

int mul(int x, int y) {
  return 1LL * x * y % MOD;
}

int main() {
  ios:: sync_with_stdio(false);
  cin.tie();
  int n;
  cin >> n;
  vector<int> a(n + 1);
  vector<int> sum(n + 1, 0);
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    sum[i] = add(sum[i - 1], a[i]);
    ans = add(ans, mul(a[i], sum[i - 1]));
  }
  cout << ans;


  return 0;
}




Measured memory_bytes: 4784
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long int
#define ordered_set tree < ll ,  null_type ,  less<ll> ,  rb_tree_tag ,  tree_order_statistics_node_update >
//added two more functions to set
//(1)*(set.find_by_order(k))[kth element in the sorted set] 
//(2)set.order_of_key(k)[count of elements strictly less than k]
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > ii;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(auto i = (c).begin(); i != (c).end(); i++)//remember i is an iterator
#define present(c,x) ((c).find(x) != (c).end())//for sets,maps,multimaps
#define cpresent(c,x) (find(all(c),x) != (c).end())//for vectors
#define tc(t) int (t); cin>>(t);while((t)--)
#define ff first
#define ss second
#define mp make_pair
#define ld long double
#define ull unsigned long long int
#define mod 1000000007
int main()
{
    ios_base::sync_with_stdio(false);//this works only
    cin.tie(NULL);// when first all inputs are from user
    cout.tie(NULL);//you will see all outputs afterwards
    ll a,b,c;
    cin>>a>>b>>c;
    ll tmp=a;
    a=max((ll)0,a-c);
    if(a==0)
    {
    	c-=tmp;
    	b=max((ll)0,b-c);
    }
    cout<<a<<" "<<b;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
/*
肥料の種類	n	<=100
与える回数	m	<=100
*/
int main(){
	
	for(int n,m;cin>>n>>m,n;){
		double data[100][100];//直前/投与
		double now[100],tmp[100];
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				cin>>data[i][j];
			}
		}
		for(int i=0;i<n;i++)now[i]=tmp[i]=1.0;
		for(int i=1;i<m;i++){
			for(int k=0;k<n;k++){//直後
				for(int j=0;j<n;j++){//直前
					if(!k)tmp[j]=now[k]*data[k][j];
					else tmp[j]=max(tmp[j],now[k]*data[k][j]);
				}
			}
			for(int j=0;j<n;j++)now[j]=tmp[j];
		}
		for(int i=1;i<n;i++){
			now[0]=max(now[0],now[i]);
		}
		printf("%.2f\n",now[0]);
	}
	
	return 0;
}


Measured memory_bytes: 1324
while True:
    e = int(input())
    if e == 0:
        break
    z, ans = 0, float('inf')
    for z in range(e):
        if z ** 3 > e:
            break
        else:
            r = e - z ** 3
            y = int(r ** 0.5)
            x = r - y ** 2
            ans = min(ans, x + y + z)
    print(ans)


Measured memory_bytes: 5720
#include<iostream>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm> 
#include<climits>
#include<stack>
#include<queue>
#include<set>
#include<cctype>
#include<bitset> 
#include<type_traits>
#include<numeric>
#include<array>
using namespace std;

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
typedef long long int ll;
typedef pair<int,int> P_ii;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

const int mod = 1000000007;
const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

void addM(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}

// a^b mod M
long myPow(long a,long b,int M) {
    long ret = 1;
    long tmp = a;
    while(b>0) {
        if((b&1)==1) ret = (ret * tmp) % M;
        tmp = (tmp * tmp) % M;
        b = b>>1;
    }
    return ret;
}

 // nCk mod M
int nCk(int n,int k,int M) {
    long ret = 1;
    int mi = min(k, n-k);
    for(int i=1;i<=mi;i++) {
        ret = (ret * myPow(i,M-2,M)) % M;
    }
    for(int i=n-mi+1;i<=n;i++) {
        ret = (ret * i) % M;
    }
    return (int)ret;
}

int main(){

    int N,W;cin >> N >> W;

    auto dp = make_vec<ll>(N+1,W+1);
    fill_v(dp,0);

    vector<ll> weight(N),value(N);
    REP(i,N) cin >> weight[i] >> value[i];

    REP(i,N) REP(j,W+1){
        if(j < weight[i]) {
            dp[i+1][j] = dp[i][j];
        } else {
            dp[i+1][j] = max(dp[i][j],dp[i][j-weight[i]]+value[i]);
        }
    }

    pl(dp[N][W])

    return 0;
}

Measured memory_bytes: 80256
a,b,c,d,e,f=map(int,input().split())

water_g=[]
for i in range(f//100+1):
  for j in range(f//100+1):
#    print(i,j)
    w=100*a*i + 100*b*j
    if w<=f:
      water_g.append(w)
    else:
      break
water_g=sorted(list(set(water_g)),reverse=True)

sugar_g=[]
for i in range(f*e//100):
  for j in range(f*e//100):
    s=c*i + d*j
    if s<=f:
      sugar_g.append(s)
    else:
      break
sugar_g=sorted(list(set(sugar_g)),reverse=True)

#print(water_g, sugar_g)

ans_water=100*a
ans_sugar=0
for water in water_g:
  if water==0:
    break
  for sugar in sugar_g:
    if water+sugar<=f and sugar/water<=e/100:
      if sugar/(sugar+water)>ans_sugar/(ans_sugar+ans_water):
        ans_water=water
        ans_sugar=sugar
print(ans_water+ans_sugar,ans_sugar)

Measured memory_bytes: 12440
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define F first
#define S second
void bst(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

vector<vector<ll> > g;
vector<bool> used;
const ll mod = (long long)1e9 + 7;
ll dp[2][(int)1e5 + 100];
void dfs(ll v,ll p = -1){
	for(ll i = 0;i < g[v].size();i++){
		ll to = g[v][i];
		if(p == to)continue;
		dfs(to, v);
		ll b = ((dp[0][to]) % mod + (dp[1][to]) % mod)% mod;
		dp[0][v] *= b;
		dp[1][v] *= (dp[0][to]) % mod;
		dp[0][v] %= mod;
		dp[1][v] %= mod;
	}
}
int main() {
	bst();
	ll n;
	cin>>n;
	if(n == 1)cout<<2,exit(0);
	g.resize(2 * n + 1);
	used.resize(n + 1);
	for(ll i = 0;i < n - 1;i++){
		ll a,b;
		cin>>a>>b;
		a--,b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(ll i = 0;i < n;i++){
		dp[0][i] = 1;
		dp[1][i] = 1;
	}
	dfs(0);
	cout<<(dp[0][0] + dp[1][0]) % mod;
	return 0;
}

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

int main(){

 int N;
 cin >> N;

 if (N%2 ==0) cout << 0.5 << endl;

 else{
   cout << (1 - (N-1.0)/ (2.0*N)) << endl;
 }

 return 0;
}


Measured memory_bytes: 256
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b); }

const int MAXN = 100000;

int n, want;
int x[MAXN];

int pos[MAXN], npos;
int neg[MAXN], nneg;

void run() {
	scanf("%d%d", &n, &want);
	REP(i, n) scanf("%d", &x[i]);

	npos = nneg = 0; REP(i, n) if (x[i] < 0) neg[nneg++] = -x[i]; else pos[npos++] = x[i]; reverse(neg, neg + nneg);
	int ret = INT_MAX;
	REPE(a, npos) { 
		int b = want - a; if (b<0 || b>nneg) continue;
		int lft = b == 0 ? 0 : neg[b - 1], rgt = a == 0 ? 0 : pos[a - 1], cur = lft + rgt + min(lft, rgt);
		ret = min(ret, cur);
	}
	printf("%d\n", ret);
}

int main() {
	run();
	return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;

const int mx=1e6+11;
const double PI = acos(-1);
#define MOD 1000000007


#define nl '\n'
#define pb push_back
#define F first
#define S second
#define I insert
#define mp make_pair

#define sz(x) x.size()
#define tt int t; cin>>t; while(t--)
#define lo(i,a,b) for(int i=a;i<b;i++)
#define rlo(i,n) for(int i=n-1;i>=0;i--)
#define be(a) (a).begin(),(a).end()
#define rbe(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a,b,sizeof(a))
#define pr(a) {for(auto x:a)cout<<x<<" ";cout<<nl;}

#define su ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define frac cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
void faltu () {            cerr << endl;}
template < typename T, typename ... hello>void faltu( T arg, const hello &... rest) {cerr << arg << ' ';faltu(rest...);}

void f()
{
  int n;
  cin>>n;
  ll a[n];
  lo(i,0,n)
  cin>>a[i];
  sort(a,a+n);
  cout<<a[n-1]-a[0]<<nl;
}

int main()
{
    su;
    f();
    return 0;
}


Measured memory_bytes: 3624
from itertools import product
n, a, b, c = map(int, input().split())
L = [int(input())for _ in range(n)]

INF = 10**18
ans = INF
for subset in product(range(4), repeat=n):
    cost = 0
    ABC = [[]for _ in range(3)]
    for i, s in enumerate(subset):
        if not s:
            continue
        ABC[s-1].append(L[i])
    if any(not X for X in ABC):
        continue
    for x, X in zip((a, b, c), ABC):
        cost += (len(X)-1)*10
        cost += abs(x-sum(X))
    if cost < ans:
        ans = cost

print(ans)


Measured memory_bytes: 8888
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <iomanip>

#define ll long long
#define ld long double
#define ull unsigned long long
#define endl "\n"
#define MohamedMotaz ios::sync_with_stdio(0); cin.tie(0); ios_base::sync_with_stdio(0);
#define f(a, b, c) for(int a = b; a < c; a++)
#define fr(a, b, c) for(int a = b; a >= c; a--)
#define all(a) a.begin(), a.end()
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pair<ll,ll>>
#define vi vector<int>
#define pi acos(-1)

using namespace std;

const ll mod = 1e9 + 7;

ll fact[1000001]; ll inv[1000001];
//ll primes[100007];
ll arr[1000007];
ll modPower(ll b, ll p) {
	if (p == 0)
		return 1;

	ll halfpow = modPower(b, p / 2);
	ll toReturn = (halfpow * halfpow) % mod;
	if (p % 2)
		toReturn = (toReturn * b) % mod;

	return toReturn;
}
//
//ll fastPower(ll b, ll p) {
//	if (p == 0)
//		return 1;
//	ll ans = fastPower(b, p / 2);
//	ans = (ans * ans);
//	if (p % 2 != 0)
//		ans = (ans * b);
//	return ans;
//}
//ll GcdRecursive(ll a, ll b) {
//	if (b == 0) return a;
//	return GcdRecursive(b, a % b);
//}
//ll modLCM(ll a, ll b) {
//	ll val = GcdRecursive(a, b);
//	ll tmp = ((a % mod) * (b % mod)) % mod;
//	ll finalVal = ((tmp % mod) * (arr[val] % mod)) % mod;
//	return finalVal;
//
//}
//ll LCM(ll a, ll b) {
//	return (a * b) / GcdRecursive(a, b);
//}
//void move1step(ll& a, ll& b, ll q) { // a and b by reference
//	ll c = a - q * b;
//	a = b;
//	b = c;
//}
//ll GcdIterative(ll a, ll b) {
//	while (b) move1step(a, b, a / b);
//	return a;
//}
//
void pre(ll n) {

	fact[0] = 1;
	inv[0] = 1;

	for (ll i = 1; i <= n; i++) {
		fact[i] = (i * fact[i - 1]) % mod;
		inv[i] = modPower(fact[i], mod - 2);
		arr[i] = modPower(i, mod - 2);
	}
}
//
//ll npr(ll n, ll r) {
//	return ((fact[n] * inv[n - r]) % mod);
//}
//
ll ncr(ll n, ll r) {
	return ((((fact[n] * inv[n - r]) % mod) * inv[r]) % mod);
}

//void sieve(ll val) {
//	memset(primes, 1, sizeof primes);
//	primes[0] = primes[1] = false;
//	for (int i = 2; i <= val; i++) {
//		if (primes[i]) {
//			for (int j = i * i; j <= val; j += i) {
//				primes[j] = 0;
//			}
//		}
//	}
//
//}

const ll MOD = 998244353;
//const ll mod = 1e9 + 7;
const ll N = 1e3 + 7;
const ll inf = 1e18 + 5;



ll n, k;
int main() {
    MohamedMotaz
    pre(3000);
    cin >> n >> k;
    ll red = n - k, blue = k;
    //val to arrange blue balls & red balls
    ll a, b, ans;
    f(i,1,k + 1){
        a = ncr(red + 1, i);
        b = ncr(blue - 1 , i - 1);
        ans = a * b;
        //cout << a << " " << b << endl;
        cout << ans % mod << endl;
    }
}







Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int q;
    cin >> q;
    map<string, int> mp;
    for(int i = 0; i < q; i++)
    {
        int com, x;
        string key;
        cin >> com >> key;
        if(com == 0)
        {
            cin >> x;
            mp[key] = x;
        }
        else if(com == 1)
        {
            auto itr = mp.find(key);
            if(itr != mp.end()) cout << itr->second << endl;
            else cout << 0 << endl;
        }
        else if(com == 2)
        {
            mp.erase(key);
        }
    }
    return 0;
}




Measured memory_bytes: 25756
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,a=0,b=0,c=0,d=0,i;
    cin>>n;
    string s1="AC",s2="WA",s3="TLE",s4="RE",s;
    for(i=0; i<n; i++)
    {
        cin>>s;
        if(s==s1)
            a++;
        if(s==s2)
            b++;
        if(s==s3)
            c++;
        if(s==s4)
            d++;

    }
    cout<<s1<<" x "<<a<<endl;
    cout<<s2<<" x "<<b<<endl;

    cout<<s3<<" x "<<c<<endl;

    cout<<s4<<" x "<<d<<endl;

}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<int, int>;
using V = vector<int>;
using VV = vector<vector<int>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
int Inf = (1<<30);
ll inf = (1LL<<60);
int main() {
	int n;
	cin >> n;
	int p;
	cin >> p;
	V a(n);
	int i;
	for (i = 0; i < n; i++) {
		cin >> a[i];
	}
	VVL dp(55, VL(2, 0));
	dp[0][0] = 1;
	for (i = 0; i < n; i++) {
		for (int j = 0; j <= 1; j++) {
			dp[i + 1][j] += dp[i][j];
			dp[i + 1][(j + a[i]) % 2] += dp[i][j];
		}
	}
	cout << dp[n][p];
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
 
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vs = vector<string>;
using vd = vector<double>;
using ul = unsigned long;
 
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }
 
const int mod=1e9+7;
 
struct mint {
  ll x;
  mint(ll x=0):x(x%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
};
 
mint c[4005][4005];
void init() {
  c[0][0] = 1;
  for (int i = 0; i <= 4000; i++) {
    for (int j = 0; j <= i; j++) {
      c[i+1][j] += c[i][j];
      c[i+1][j+1] += c[i][j];
    }
  }
}
mint comb(int n, int k) {
  return c[n][k];
}
 
bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;
 
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
 
    return true;
}
 
map<ll, ll> primeFact(ll n) {
  map<ll, ll> res;
  for (ll i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      res[i]++;
      n /= i;
    }
  }
  if (n != 1) res[n]++;
  return res;
}
 
void printv(vi& v){
  rep(i,v.size()) cout << v[i] << " ";
  cout << endl;
}
void printv(vll& v){
  rep(i,v.size()) cout << v[i] << " ";
  cout << endl;
}
int vtotal(vi& v){
  int total=0;
  rep(i,v.size()) total+=v[i];
  return total;
}
 
int main()
{
  //init(); // mint初期化
  cin.tie( 0 );
  ios::sync_with_stdio( false );
  int n,a,b;
  cin>>n>>a>>b;
  int ans=n*a;
  if(ans>b)ans=b;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 125568
#include <stdio.h>

int main(){
   int n,i,j,a[200000],b[200000];
   long long k;

   scanf("%d %lld",&n,&k);
   for (i=0;i<n;i++) {
      scanf("%d",&a[i]);
      a[i]--;
      b[i]=-1;
   }
   for (i=j=0;k>0;j++,k--)
      if (b[i]>=0) {
         k=k%(j-b[i]);
         for (;k>0;k--) i=a[i];
         printf("%d\n",i+1);
         return 0;
      } else {
        b[i]=j;
        i=a[i];
      }
   printf("%d\n",i+1);
   return 0;
}


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

int main(){
  int N;
  cin>>N;
  vector<tuple<string,int,int>> guido(N);
  vector<string> S(N);
  vector<int> P(N);
  for(int i=0;i<N;++i){
    cin>>S.at(i);
    cin>>P.at(i);
    guido.at(i)=make_tuple(S.at(i),100-P.at(i),i+1);
  }

  sort(guido.begin(),guido.end());
  for(int i=0;i<N;++i){
    cout<<get<2>(guido.at(i))<<endl;
  }
}

Measured memory_bytes: 256
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
class Program
{
	static void Main()
	{
		long n = long.Parse(Console.ReadLine());//long.Parseはstringをlongに変換。
    long x = 0;
    long y = 0;
    long z = 0;

    for(long a = 1; a <= 3500; a++)
    {
      for(long b = 1; b <= 3500; b++)
      {
        if(4*a*b-n*b-n*a > 0)
        {
          if((n*a*b) % (4*a*b-n*b-n*a) == 0)
          {
            x = a;
            y = b;
            z = (n*a*b) / (4*a*b-n*b-n*a);
          }
        }
      }
    }

		Console.WriteLine(x+" "+y+" "+z);//WriteLineをWriteとすると、改行なしで出力。
	}
}

Measured memory_bytes: 13140
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <numeric>
#include <cmath>
#include <iomanip> //cout << fixed << setprecision(15) << << endl;
#include <cassert>
#include "atcoder/segtree"

#define ll long long int
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
using namespace std;
using namespace atcoder;

int mx8[] = {0,0,1,-1,-1,1,-1,1};
int my8[] = {-1,1,0,0,-1,-1,1,1};
int mx4[] = {1,-1,0,0};
int my4[] = {0,0,-1,1};
const int MOD = 1000000007;
ll op(ll a, ll b) {
    return max(a, b);
}
ll e() {
    return -1;
}

int v;
bool f(ll x){
    return v > x;
}

int main(){
    int n, q;
    cin >> n >> q;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];

    segtree<ll, op, e> seg(a);
    while(q--){
        int t; cin >> t;
        if(t==1)
        {
            int X,V; cin >> X >> V;
            X--;
            seg.set(X,V);
        }
        else if(t == 2)
        {
            int l, r; cin >> l >> r;
            l--;
            cout << seg.prod(l,r) << endl;
        }
        else
        {
            ll X; cin >> X >> v;
            X--;
            cout << seg.max_right<f>(X) + 1<< endl;
        }
    }

}

Measured memory_bytes: 9072
from operator import itemgetter
import heapq

N = int(input())
X = [[int(p) for p in input().split()] for _ in range(N)]

X.sort()
for i in range(N):
    X[i].append(i)
    
Y = sorted(X, key=itemgetter(1))

h = []
for i in range(N-1):
    heapq.heappush(h, (X[i+1][0]-X[i][0], i+1, i))
    heapq.heappush(h, (Y[i+1][1]-Y[i][1], Y[i+1][2], Y[i][2]))
    
    
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]
    
    
UF = UnionFind(N)
ans = 0
while h:
    t = heapq.heappop(h)
    if UF.isSameGroup(t[1], t[2]):
        continue
    ans += t[0]
    UF.unite(t[1], t[2])
    
print(ans)

Measured memory_bytes: 55384
from itertools import accumulate
n, k = map(int, input().split())
A = list(map(int, input().split()))
cumsum = [0] + list(accumulate(A, lambda x, y: x + y))
li = []
for i in range(n + 1):
  for j in range(i + 1, n + 1):
    li.append(cumsum[j] - cumsum[i])
li.sort(reverse=True)

ans = 0
# 大きい桁から見ていく
for i in reversed(range(1, 41)):
  new = []
  for s in li:
    # sはi桁目のビット+ansと同じ位置ののビットが立っているか
    if (ans + 2 ** (i - 1)) & s == ans + 2 ** (i - 1):
      new.append(s)
  # その桁のビットが立っている要素の数がkを超えたら、その桁の値をansに足す
  if len(new) >= k:
    # 条件を満たす要素だけを対象とするように更新する
    li = new
    ans += 2 ** (i - 1)
print(ans)

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

int main() {
  string s,t;
  cin >> s >> t;
  
  string x = s;
  string y;
  bool Rotation = false;
  for(int i=0; i<s.size(); i++) {
    y = x;
    x.pop_back();
    x = y[s.size()-1]+x;
    if(x == t) Rotation = true; 
  }
  if(Rotation) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

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

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
#define e_b emplace_back
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
using namespace std;
using ll = long long;
using ld = long double;
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}

int N,K;
vector<int> A;

bool isOK(int x){
  int cnt=0;
  for(int i=0;i<N;i++){
    int a=A.at(i);
    cnt+=(a+x-1)/x -1;
  }
  if(cnt<=K)  return true;
  else  return false;
}

int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  cin >> N >> K;
  A.resize(N);
  for(int i=0;i<N;i++)  cin >> A.at(i);

  int ng=0;
  int ok=1e9;
  while(abs(ok-ng)>1){
    int mid=(ok+ng)/2;
    if(isOK(mid))  ok=mid;
    else  ng=mid;
  }
  cout << ok << endl;

  return 0;
}

Measured memory_bytes: 3964
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define mp make_pair
using namespace std;

using ll = long long;
using ii = pair<int, int>;
const int INF = (int)10e9;
int N, W;
ll dp[105][100005];

int main() 
{
    //optimization
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> W;
    vector<int> w(N), v(N);

    for(int i = 0; i < N; i++) 
    {
        cin>>w[i]>>v[i];
    }

    for(int i = 0; i < N; i++) 
    {
        for(int j = 0; j <= W; j++) 
        {
            if(i == 0) 
            { 
                if(j - w[i] >= 0) 
                {
                    dp[i][j] = v[i];
                }
            }
            else if(j - w[i] >= 0) 
            {
                dp[i][j] = max(v[i] + dp[i-1][j-w[i]], dp[i-1][j]);
            }
            else 
            {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    cout<<dp[N-1][W]<<endl;

    return 0;
}

Measured memory_bytes: 80128
#include <stdio.h>
#include <vector>
#include <functional>
#include <queue>
#include <iostream>
using namespace std;
const int MAX_V=100000;
const int INF=1000000000;
int K;
struct edge {int to, cost;};
typedef pair<int,int> P;
vector<edge> G[MAX_V];
int d[MAX_V];
void dijkstra(int s){
  priority_queue<P,vector<P>,greater<P> >que;
  fill(d,d+K,INF);
  d[s]=1;
  que.push(P(1,s));
 
  while(!que.empty()){
    P p=que.top();
    que.pop();
    int v=p.second;
    if(d[v] < p.first)continue;
    for(int i=0;i < G[v].size();i++){
      edge e=G[v][i];
      if(d[e.to] > d[v]+e.cost){
	d[e.to] = d[v] + e.cost;
	que.push(P(d[e.to],e.to));
      }
    }
  }
}

int main(){
  cin >> K;
  for(int i=0;i<K;i++){
    edge e;
    e.to=(i*10)%K;
    e.cost=0;
    G[i].push_back(e);
    e.to=(i+1)%K;
    e.cost=1;
    G[i].push_back(e);
  }

  dijkstra(1);
  cout << d[0] << endl;
  return 0;
}


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

#define ll long long
const int MOD = 1e9 + 7;

void setIO(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
}

int main() {
	setIO();
	int n;cin >> n;
	int rem = n % 10;
	if(rem == 2 || rem == 4 || rem == 5 || rem == 7 || rem == 9) cout << "hon\n";
	else if(rem == 0 || rem == 1 || rem == 6 || rem == 8) cout << "pon\n";
	else cout << "bon\n";
}


Measured memory_bytes: 3648
#include<stdio.h>

int main(){
    int a, b;
    scanf("%d %d", &a, &b);
    if(a > b){
        printf("a > b\n");
    }
    if(a == b){
        printf("a == b\n");
    }
    if(a < b){
        printf("a < b\n");
    }
}


Measured memory_bytes: 2096