akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
int main(){
	int i;
	int long long m,t1=0,t2=0,t3=0,buf;
	for(i=0;i<10;i++){

	scanf("%lld",&m);
	if(m>t3){t3=m;}
	if(t3>t2){buf=t2;t2=t3;t3=buf;}
	if(t2>t1){buf=t1;t1=t2;t2=buf;}

	}
	printf("%lld\n%lld\n%lld\n",t1,t2,t3);
	return 0;



}

Measured memory_bytes: 600
import java.util.Scanner;

public class Main {
	
	static int h,w,n;
	static int []a;
	static int [][]  grid;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		 h = Integer.parseInt(sc.next());
		 w = Integer.parseInt(sc.next());
		
		 n = Integer.parseInt(sc.next());
		
		 a = new int [n+1];
		
		for(int i = 1 ;i <= n ;i++) {
			a[i] = Integer.parseInt(sc.next());
		}
		
		grid = new int [h][w];
		int x = 0; int num = 1;
		int cnt = 0;
		while(grid[h-1][w-1] == 0) {
			if(x % 2 == 0) {
				for(int i = 0 ;i < h ; i++) {
					grid[i][x] = num;
					cnt++;
					if(cnt == a[num]) {
						num++;
						cnt = 0;
					}
				}
				x++;
			}
			else {
				for(int i = h-1 ; i >= 0 ;i--) {
					grid[i][x] = num;
					cnt++;
					if(cnt == a[num]) {
						num++;
						cnt = 0;
					}
				}
				x++;
			}
		}
		for(int i = 0 ;i < h ; i++) {
			for(int j = 0 ; j < w-1 ; j++) {
				System.out.print(grid[i][j]+" ");
			}
			System.out.print(grid[i][w-1]);
			System.out.println();
		}
	}	
}


Measured memory_bytes: 27028
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vvs = vector<vs>;
using pli = pair<long long, int>;
using vpli = vector<pli>;
#define PI 3.141592653589793

int main() {
  double a, b, x, v;
  double angle = 0;
  cin >> a >> b >> x;
  v = a * a * b;

  if (x > (v / 2)) {
    double tmpv = v - x;
    double t = (tmpv * 2) / (a * a * a);
    angle = atan(t) * 180.0000000000 / PI;
  }
  else {
    double tmpv = x;
    double t = (tmpv * 2) / (a * b * b);
    angle = 90.0000000000 - (atan(t) * 180.000000000 / PI);
  }
  
  printf("%.10lf\n", angle);
}

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

int main(){
    int a, b;
    cin>>a>>b;
    if(a>b){
        cout<<"a > b"<<endl;
    }
    if(a<b){
        cout<<"a < b"<<endl;
    }
    if(a==b){
        cout<<"a == b"<<endl;
    }
}


Measured memory_bytes: 3108
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>
#include <unordered_map>

using namespace std;
typedef long long int ll;

#define SP(x) setprecision((int)x)
#define ALL(v) v.begin(), v.end()

// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a, long long m)
{
    long long b = m, u = 1, v = 0;
    while (b)
    {
        long long t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0)
        u += m;
    return u;
}

/* デカい配列はここで宣言 */

ll facctorialMethod(ll k)
{
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum %= 1000000007;
    }
    return sum;
}

ll modPow(ll a, ll x, ll p)
{
    //calculates a^x mod p in logarithmic time.
    ll res = 1;
    while (x > 0)
    {
        if (x % 2 != 0)
        {
            res = (res * a) % p;
        }
        a = (a * a) % p;
        x /= 2;
    }
    return res;
}

ll modInverse(ll a, ll p)
{
    //calculates the modular multiplicative of a mod m.
    //(assuming p is prime).
    return modPow(a, p - 2, p);
}
ll modBinomial(ll n, ll k, ll p)
{
    // calculates C(n,k) mod p (assuming p is prime).

    ll numerator = 1; // n * (n-1) * ... * (n-k+1)
    for (ll i = 0; i < k; i++)
    {
        numerator = (numerator * (n - i)) % p;
    }

    ll denominator = 1; // k!
    for (ll i = 1; i <= k; i++)
    {
        denominator = (denominator * i) % p;
    }

    // numerator / denominator mod p.
    return (numerator * modInverse(denominator, p)) % p;
}

int main(int argc, char const *argv[])
{
    ll x, y;
    cin >> x >> y;

    if ((x + y) % 3 != 0)
        cout << 0 << endl;
    else if (y > x * 2 || y * 2 < x)
        cout << 0 << endl;
    else
    {
        ll a = 0, b = 0;
        while (x != 2 * y)
        {
            x--;
            y -= 2;
            a++;
        }
        while (x != 0)
        {
            x -= 2;
            y--;
            b++;
        }
        // b = x / 2;
        ll ans = modBinomial(a + b, min(a, b), 1000000007);

        cout << ans << endl;
    }
}


Measured memory_bytes: 256
#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 n;cin >> n ;

    int odd_num=0;
    int e2_num=0;
    int e4_num=0;

    for(int i=0;i<n;i++){
        long long int tmp;cin >> tmp;
        if(tmp%2!=0) odd_num++;
        else if(tmp%4==0) e4_num++;
        else e2_num++;
    }
    if(e2_num==0){
        Yes(e4_num+1>=odd_num)
    } else {
        Yes(e4_num>=odd_num)
    }
}

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

using namespace std;
using LL = long long;
using P = pair<int, int>;

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

#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e19;
const int MOD = 1e9 + 7;

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    vector<int> sep;
    int cur = 1;
    
    FOR(i, 1, n)
    {
        if(s[i] == s[i-1])
        {
            cur++;
        }
        else
        {
            sep.push_back(cur);
            cur = 1;
        }
    }
    sep.push_back(cur);
    int m = sep.size();
    vector<int> ruiseki(m+1, 0);
    REP(i, m) ruiseki[i+1] += ruiseki[i] + sep[i];

    int ans = 0;
    bool flag = s[0] == '1';
    REP(i, m)
    {
        if(flag && i%2==0 || !flag && i%2!=0)
        {
            ans = max(ans, ruiseki[min(i+k*2+1, m)] - ruiseki[i]);
        }
        else
        {
            ans = max(ans, ruiseki[min(i+k*2, m)] - ruiseki[i]);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1272
#include <cstdio>
#include <iostream>
#include <cassert>
#include <string>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;

int main() {
    int H, W, A, B;
    scanf("%d %d %d %d", &H, &W, &A, &B);
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (i < B) {
               if (j < A) printf("1");
               else printf("0");
            } else {
               if (j < A) printf("0");
               else printf("1");
            }
        }
        puts("");
    }
    return 0;
}


Measured memory_bytes: 1280
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
using ll = long long;

int main() {
    ll n;
    cin >> n;
    vector<ll> a(n),b(n);
    for(auto &aa:a) cin >> aa;
    for (int j=0;j<n;j++) b[j] = a[j] - (j+1);
    sort(b.begin(),b.end());
    ll hb = b[n/2], ans = 0;
    for (auto bb:b) ans += abs(bb - hb);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3328
#include<stdio.h>

int main()
{
	int a,b,c,ans1,ans2, ans3,temp,temp2,temp3;
	scanf("%d %d %d", &a, &b, &c);
	temp = a;
	a = 0;
	if(c>b)
        ans1 = c-b;
	else
        ans1 = b-c;

	temp2 = b;
	b = 0;
	if(c>temp)
        ans2 = c-temp;
	else
        ans2 = temp-c;

	temp3 = c;
	c = 0;
	if(temp>temp2)
        ans3 = temp-temp2;
	else
        ans3 = temp2-temp;

	if(ans1>=ans2 && ans1>=ans3)
        printf("%d\n", ans1);
    else if(ans2>=ans1 && ans2>=ans3)
        printf("%d\n", ans2);
    else
        printf("%d\n", ans3);
    return  0;

}




Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1000000010
#define EPS 1e-9
#define fst first
#define scd second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  int now=INF;
  int ans=0;
  rep(i,n){
    int num;
    cin>>num;
    if(num<now){
      now=num;
      ans++;
    }
  }
  cout<<ans<<endl;

  return 0;
}


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


int main(){
  //浮動小数点を含むと精度が足りない
  ll a;
  int x;
  double b;
  cin >> a >> b;

  x = 100*b+0.5;

  a = a*x;
  a/=100;

  cout << a << endl;
  return 0;

}


/*
int main(){
  ll x;
  int y,z;
  scanf("%lld%d%*c%d",&x,&y,&z);
  x = x*(y*100+z);
  x/=100;
  printf("%lld\n",x);
  return 0;
}
*/


Measured memory_bytes: 3712
M=1000000007
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
dp=[[0]*256 for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
    _dp=dp
    for l in reversed(range(1,i+2)):
        for j in range(256):
            _dp[l][j]+=dp[l-1][a[i]^j]
    dp=_dp
p=[1]*(n+1)
for i in range(1,n+1):
    p[i]=p[i-1]*i%M
print sum([dp[l][k]*p[l] for l in range(1,n+1)])%M


Measured memory_bytes: 22044
#include "cstdio"
#include "string.h"

int C[32];
int M[32];
int main()
{
    int n;
    char c;
    while (scanf("%d",&n) != EOF)
    {
        memset(C,0,sizeof(M));
        getchar();
        for (int i=0;i<n;i++)
        {
            memset(M,0,sizeof(C));
            while (c = getchar())
            {
                if (c == '\n')
                {
                    break;
                }
                M[int(c-'a')]++;
            }
            for (int k=0;k<26;k++)
            {
                if (i==0 || M[k]<C[k])
                {
                    C[k] = M[k];
                }
            }
        }
        for (int i=0;i<26;i++)
        {
             while (C[i]-->0)
             {
                 printf ("%c",char(i+'a'));
             }
        }
        putchar('\n');
    }
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'

using namespace std;

main()
{
    fast;
    int n,ans=0,i;
    ll h,w,a,b;
    cin>>n>>h>>w;
    for (i=0;i<n;i++)
    {
        cin>>a>>b;
        if (a>=h && b>=w)
            ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const ll INFLL = 4*1001001001001001001;
const int MOD = (int)1e9 + 7;
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;

int main () {
    
    int n; cin >>n;
    vector<int> p(n); REP(i,n) cin >> p[i];

    int count = 0;
    for (int i = 1; i < n-1; i++) {
        int s = p[i-1];
        int t = p[i+1];
        int mn = min(s, min(t, p[i]));
        int mx = max(s, max(t, p[i]));
        if (mn != p[i]) {
            if (mx == p[i] && (t == mx || s == mx)) {
                count++;
            } else if (mx != p[i]) {
                count++;
            } 
        } 
    }

    cout << count << endl;

    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
typedef long long int ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<signed(n);i++)
#define EREP(i,n) for(int i=1;i<=signed(n);i++)
#define ALL(a) (a).begin(),(a).end()
using std::cout;
using std::vector;
using std::endl;
using std::cin;
using std::string;
//#define EVEL 1
#ifdef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
const int MOD = 1000000007;
const ll INF = 50000000000000000;
typedef std::pair<int,int> P;
struct edge {int to,cost;};
    int N,M,R;
    int r[10];
    vector<edge> G[1000];
    ll d[1000][1000];
    ll ans;

    void warshall_floyd(int n) { // nは頂点数
      for (int i = 0; i < n; i++)      // 経由する頂点
        for (int j = 0; j < n; j++)    // 開始頂点
          for (int k = 0; k < n; k++)  // 終端
            d[j][k] = std::min(d[j][k], d[j][i] + d[i][k]);
    }


int main(){
    std::ios_base::sync_with_stdio(false);
    cin>>N>>M>>R;
    REP(i,R)cin>>r[i];
    REP(i,1000)REP(j,1000)d[i][j]=INF;
    REP(i,M){
        int a,b,c;
        cin>>a>>b>>c;
        d[a-1][b-1]=c;
        d[b-1][a-1]=c;
    }
    REP(i,N)d[i][i]=0;
    warshall_floyd(N);
    std::sort(r,r+R);
    ans=INF;
    do{
        ll temp=0;
        REP(i,R-1){
            DEB(r[i])DEB(r[i+1])
            DEB(d[r[i]-1][r[i+1]-1])END
            temp+=d[r[i]-1][r[i+1]-1];
        }
        DEB(temp)END
        ans=std::min(ans,temp);
    }while(std::next_permutation(r,r+R));

    cout<<ans<<endl;
    return 0;
}
//ABC 073 D - joisino's travel


Measured memory_bytes: 8064
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>
 
using namespace std;
using std::cout;
using ll =long long;
bool is_int_lround(double x){
  return std::lround(x)==x;
}
int ketasuu(int x){
  int n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}
ll gcd11(ll x, ll y){
  long long a= max(x,y), b=min(x,y), c=a%b;
  while( c!=0){
    a =b;
    b =c;
    c = a%b;
  }
  return b;
}

int ab(int x, int y){
  if(x>=y){
    return x-y;
  }
  else if(y>x){
    return y-x;
  }
}
int main(){
  int n;
  cin >>n ;
  vector<int> L(n);
  int tot=0;
  for(int i ;i<n;i++){
    cin>> L[i];
    tot += L[i];
  }
  sort( L.begin() , L.end() );
  if(2*L[n-1]< tot){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
    

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

struct UnionFind{
  vector<int> d;
  UnionFind(int n) : d(n, -1){}
  int find(int x){
    if(d.at(x) < 0) return x;
    return d.at(x) = find(d.at(x));
  }
  bool unite(int x, int y){
    x = find(x); y = find(y);
    if(x == y) return false;
    if(d.at(x) > d.at(y)) swap(x, y);
    d.at(x) += d.at(y);
    d.at(y)= x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -d.at(find(x)); }
};

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> p(n);
  rep(snip_i, n) cin >> p.at(snip_i);
  UnionFind uf(n);
  rep(i, m){
    int a, b;
    cin >> a >> b;
    a--; b--;
    uf.unite(p.at(a)-1, p.at(b)-1);
  }
  int ans = 0;
  rep(i, n){
    if(uf.same(i, p.at(i)-1)) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
import java.io.*;
import java.util.*;

class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        
        boolean[][] cardHasFlag = new boolean[4][13];
        
        int cardNum = sc.nextInt();
        
        for (int i = 0; i < cardNum; i++) {
            String sign = sc.next();
            int card = sc.nextInt();
            
            switch(sign) {
                case "S" :
                    cardHasFlag[0][card-1] = true;
                    break;
                case "H" :
                    cardHasFlag[1][card-1] = true;
                    break;
                case "C" :
                    cardHasFlag[2][card-1] = true;
                    break;
                case "D" :
                    cardHasFlag[3][card-1] = true;
                    break;
            }
        }
        
        for (int i = 0; i < 4; i++) {
            for (int j = 0 ; j < 13; j++) {
                if (cardHasFlag[i][j] == false) {
                    switch (i) {
                        case 0 :
                            System.out.printf("S %d\n", j+1);
                            break;
                        case 1 :
                            System.out.printf("H %d\n", j+1);
                            break;
                        case 2 :
                            System.out.printf("C %d\n", j+1);
                            break;
                        case 3 :
                            System.out.printf("D %d\n", j+1);
                            break;
                    }
                }
            }
        }
    }
}

Measured memory_bytes: 26320
#include <iostream>
using namespace std;
int main(void){
    string s;
    std::cin >> s;
    bool isgood = true;
    if (s[0] == s[1]) isgood = false;
    if (s[1] == s[2]) isgood = false;
    if (s[2] == s[3]) isgood = false;
    
    if (isgood) {
        cout << "Good" << endl;
    } else {
        cout << "Bad" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    int max=-100000;
    if(max<a+b) max=a+b;
    if(max<a-b) max=a-b;
    if(max<a*b) max=a*b;
    printf("%d\n",max);
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int n,h;
int a[100010],b[100010];
int main()
{
	cin>>n>>h;
	for(int i=0;i<n;i++)
	{
		cin>>a[i]>>b[i];
	}
	sort(a,a+n);
	sort(b,b+n);
	int ans=0;
	for(int i=0;i<n;i++)
	{
		if(h<=0)
		{
			cout<<ans;
			return 0;
		}
		if(b[n-i-1]>=a[n-1])
		{
			h-=b[n-i-1];
			ans++;
		}
		else
		  break;
	}
	cout<<ans+(h+a[n-1]-1)/a[n-1];
	return 0;
}

Measured memory_bytes: 1152
#include<stdio.h>

int main()
{
	int n,x,kaizyo=1;

	for(;;)
	{
		scanf("%d",&n);
		if(n<=20)
		{
			break;
		}
	}

	if(n==1)
	{
		kaizyo=1;
		printf("%d\n",kaizyo);
	}
	else if(n<=16)
	{
		for(x=1;x<=n;x++)
		{
			kaizyo*=x;
		}
		printf("%d\n",kaizyo);
	}
	else if(n==17)
	{
		printf("355687428096000\n");
	}
	else if(n==18)
	{
		printf("6402373705728000n");
	}
	else if(n==19)
	{
		printf("121645100408832000\n");
	}
	else if(n==20)
	{
		printf("2432902008176640000\n");
	}
	return 0;
}

Measured memory_bytes: 1004
#include<cstdio>
#include<algorithm>
#include<climits>
using namespace std;
static const int MAX_P = 100000;

int p;
int num[MAX_P];
int memo[MAX_P];

int main(){
	scanf("%d", &p);
	for(int j = 0; j < p; j++){
		scanf("%d", &num[j]);
	}
	reverse(num, num + p);
	fill(memo, memo + p, INT_MAX);
	int res = 0;
	for(int j = 0; j < p; j++){
		*upper_bound(memo, memo + p, num[j]) = num[j];
	}
	printf("%d\n", lower_bound(memo, memo + p, INT_MAX) - memo);
	return 0;
}


Measured memory_bytes: 896
#include <iostream>
#include <iomanip>
#include <string>
#include <unordered_map>
#include <cmath>
#include <algorithm>

typedef long long ll;
typedef long double ld;

using namespace std;
int main()
{
  ll k, sum = 0;
  cin >> k;
  for (int a = 1; a <= k; a++)
  {
    for (int b = 1; b <= k; b++)
    {
      for (int c = 1; c <= k; c++)
      {
        sum += __gcd(__gcd(a, b), c);
      }
    }
  }

  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 3640
using namespace std;

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include <utility>
#include <functional>
#include <queue>
#include <cmath>
#include <numeric>
#include <map>
using namespace std;


int main(void){
	long long int N, M, Lm = 0, Rm = 100000;

	cin >> N >> M;

	vector<long long int> A,B, C;
  multimap<long long int,long long int> CB;
	while (N--) {
		long long int tmp;
		cin >> tmp;
		A.push_back(tmp);
	}
	while (M--) {
		long long int L, R;
		cin >> L >> R;
		B.push_back(L);
		C.push_back(R);
      CB.emplace(R,L);

	}
		sort(A.begin(), A.end());
  auto Ait = A.begin();
  long long int r = 0LL;
  for (auto it = CB.rbegin();it != CB.rend();++it) {
    auto Amin = lower_bound(A.begin(), A.end(), it->first);
		if (Ait + it->second < Amin) {
          Ait += it->second;
          r += it->first * it->second;
        }
        else {
          r += it->first * (Amin - Ait);
          Ait = Amin;
          break;
        }
  }
	cout << r + accumulate(Ait, A.end(), 0LL) << endl;
	return 0;
}


Measured memory_bytes: 8820
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*(10**5)+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
a,b=map(int,input().split())
c=min(a,b)
s=0
for i in range(0,c+1):
    s+=cmb(a,i,10**9+7)*cmb(a-1,i,10**9+7)
print(s%(10**9+7))

Measured memory_bytes: 33176
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    int h[100010];
    rep(i, N) cin >> h[i];
    int dp[100010];
    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);
    rep(i, N - 2) {
        int step1 = abs(h[i + 2] - h[i + 1]);
        int step2 = abs(h[i + 2] - h[i]);
        dp[i + 2] = min(step1 + dp[i + 1], step2 + dp[i]);
    }
    cout << dp[N - 1] << endl;

    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    if(s[0]==s[1]||s[1]==s[2]||s[2]==s[3]){
        cout<<"Bad"<<endl;
    }
    else{
        cout<<"Good"<<endl;
    }
}

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

num_list = [0]*(n+1)
num_list[0] = 2
num_list[1] = 1
for i in range(2, n+1,1):
  num_list[i] = num_list[i-1] + num_list[i-2]

ans = num_list[n]
print(ans)

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

int main()
{
    int d;
    cin >> d;
    vector<int> c(26);
    vector<vector<int>> s(d,vector<int>(26));

    for (int i = 0; i < 26; i++)
    {
        cin >> c[i];
    }
    for (int i = 0; i < d; i++)
    {
        for (int j = 0; j < 26; j++)
        {
            cin >> s[i][j];
        }
    }
    vector<int> t(d);
    for (int i = 0; i < d; i++)
    {
        cin >> t[i];
    }
    
    int m;
    cin >> m;
    while(m--){
        int dd,p;
        cin >> dd >> p;
        t[dd - 1] = p;
        long long ans = 0;
        vector<int> last(26,0);
        for (int i = 0; i < d; i++)
        {
            ans += s[i][t[i] - 1];
            last[t[i] - 1] = i + 1;
            for (int j = 0; j < 26; j++)
            {
                ans -= c[j] * (i + 1 - last[j]);
            }
            
        }
        cout << ans << endl;
    }


}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

#define repa(i, a, b) for (auto i = (a); i <= (b); i++)
#define repd(i, a, b) for (auto i = (a); i >= (b); i--)
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define zero(a)  memset((a), 0, sizeof (a))
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back

constexpr auto inf = numeric_limits<int>().max();
constexpr auto llinf = numeric_limits<ll>().max();

template<typename ForwardIterator>
void dump(ForwardIterator st, ForwardIterator en) {
	for (auto it = st; it != en; it++) {
		cout << *it << " ";
	}
	cout << endl;
}

template<typename ForwardIterator>
void dump_map(ForwardIterator st, ForwardIterator en) {
	for (auto it = st; it != en; it++) {
		cout << (*it).first << ":" << (*it).second << " ";
	}
	cout << endl;
}

template<typename T>
void debug(initializer_list<T> list) {
  for (auto el : list) {
    cout << el << " ";
  }
  cout << endl;
}

void solve() {
	ll n;
	cin >> n;
	vector<ll> divs(n + 5, 1LL);
	repa(i, 2LL, n) {
		for (auto j = i; j <= n; j += i) {
			divs[j]++;
		}
	}
	auto sum = 0LL;
	repa(i, 1LL, n) {
		sum += i * divs[i];
	}
	cout << sum;
	cout << "\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 81336
N = int(input())
S = [input() for i in range(N)]
mydict = {}
for i in range(N):
    if S[i] not in mydict.keys():
        mydict[S[i]] = 1
    else:
        mydict[S[i]] += 1
sortedDict = sorted(mydict.items(), key=lambda x:x[1], reverse=True)
mylist = [sortedDict[0][0]]
length = len(sortedDict)
if(length > 1):
    for i in range(length-1):
        if sortedDict[i][1] == sortedDict[i+1][1]:
            mylist += [sortedDict[i+1][0]]
            i += 1
        else: break
    mylist.sort()
for i in range(len(mylist)):
    print(mylist[i])

Measured memory_bytes: 48496
#include <stdio.h>
#include <string.h>
 
int main()
{
    int n;
    char *p;
    char str[1000];
    scanf("%d\n",&n);
    while(n--){
    gets(str);
    for(p;p=strstr(str,"Hoshino");)p[6]='a';
    puts(str);
    }
    return 0;
}

Measured memory_bytes: 1012
import sys
def t(A,p,r):
 x=A[r][1];i=p-1
 for j in range(p,r):
  if A[j][1]<=x:
   i+=1;A[i],A[j]=A[j],A[i]
 A[i+1],A[r]=A[r],A[i+1]
 return i+1
def k(A,p,r):
 if p<r:
  q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def s(A):
 for i in range(n-1):
  if A[i][1]==A[i+1][1]:
   if A[i][2]>A[i+1][2]:
    return'Not s'
 return'S'
n=int(input())
f=lambda x,y:(x,int(y))
A=[(*f(*e.split()),i)for i,e in enumerate(sys.stdin)]
k(A,0,n-1)
for e in[[s(A)+'table']]+A:
 print(*e[:2])


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

int main() {
  int n;
  cin >> n;
  double sum = 0;
  for (int i = 0; i < n; ++i) {
    double x;
    string y;
    cin >> x >> y;
    if (y == "BTC") {
      sum += x * 380000;
    } else {
      sum += x;
    }
  }
  cout << fixed << setprecision(15);
  cout << sum << endl;
}


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

int N, Q;
string S;
int l[100000];
int r[100000];
int t[100000];

int main(){
	cin >> N >> Q;
	cin >> S;
	for (int i = 0; i < Q; ++i) cin >> l[i] >> r[i];
	if((S[0] == 'A') && (S[1] == 'C')){
		t[0] = 1;
	}else{
		t[0] = 0;
	}
	for(int i = 1; i < N; ++i){
		if((S[i] == 'A') && (S[i+1] == 'C')){
			t[i] = t[i-1] + 1;
		}else{
			t[i] = t[i-1];
		}
	}
	for(int i = 0; i < Q; ++i){
		cout << t[r[i] - 2] - t[l[i] - 2] << endl;
	}
}

Measured memory_bytes: 2304
// C-Coloring Colorfully

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(void){
    
    string S;
    cin >> S;
    int A1=0;
    int A2=0;
    for(int i=0;i<S.size();++i){
        if(i%2==0){
            if(S[i]=='0'){
                A1++;
            }
            if(S[i]=='1'){
                A2++;
            }
        } else {
            if(S[i]=='0'){
                A2++;
            }
            if(S[i]=='1'){
                A1++;
            }
        }
    }
    cout << min(A1,A2) << endl;
    return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
#include <math.h>

struct Point { double x, y; };

void koch(int n, Point a, Point b) {
	if(n == 0){
		return;
	}
	
	Point s, t, u;
	double th = M_PI * 60.0 / 180.0;
	
	s.x = (2.0 * a.x + 1.0 * b.x) / 3.0;
	s.y = (2.0 * a.y + 1.0 * b.y) / 3.0;
	t.x = (1.0 * a.x + 2.0 * b.x) / 3.0;
	t.y = (1.0 * a.y + 2.0 * b.y) / 3.0;
	u.x = (t.x - s.x) * cos(th) - (t.y - s.y) * sin(th) + s.x;
	u.y = (t.x - s.x) * sin(th) + (t.y - s.y) * cos(th) + s.y;
	
	koch(n - 1, a, s);
	printf("%.8f %.8f\n", s.x, s.y);
	koch(n - 1, s, u);
	printf("%.8f %.8f\n", u.x, u.y);
	koch(n - 1, u, t);
	printf("%.8f %.8f\n", t.x, t.y);
	koch(n -1, t, b);
}

int main() {
	Point a, b;
	int n;
	
	scanf("%d", &n);
	
	a.x = 0;
	a.y = 0;
	b.x = 100;
	b.y = 0;
	
	printf("%.8f %.8f\n", a.x, a.y);
	koch(n, a, b);
	printf("%.8f %.8f\n", b.x, b.y);
	
	return 0;
}

Measured memory_bytes: 2684
N = int(input())
K = int(input())
x = list(map(int, input().split()))

ans = 0

for i in range(N):
    dist_zero = x[i] - 0
    dist_K = abs(x[i] - K)
    if dist_zero <= dist_K:
        ans += dist_zero * 2
    else:
        ans += dist_K * 2

print(ans)


Measured memory_bytes: 9076
#include <iostream>

using namespace std;

int parent[1000000];

bool done[100000];

int find_root(int x){
	if(parent[x] != x){
     	x = parent[x] = find_root(parent[x]);
    }
  
  return x;
}

void same(int x, int y){
  int xx = find_root(x);
  int yy = find_root(y);
  parent[yy] = xx;
}



int main(){
  int n, m, x, y, z;
  cin >> n >> m;
  for(int i = 0; i < n;i++){
      parent[i] = i;
  }
  for(int i = 0; i < m;i++){
  	cin >> x >> y >> z;
    x--;
    y--;
  	same(x,y);
  }
  int ret = 0;
  for(int i = 0;i<n;i++){
  	int tmp = find_root(i);
    if(!done[tmp]){
    	ret++;
      	done[tmp] = true;
    }
  }
  cout << ret << endl;
  return 0;

}

Measured memory_bytes: 768
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    K = int(_in[0])  # type:int
    S =     _in[1]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    if len(S)<=K:
        s = S
    else:
        s = S[:K]+'...'
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(s)


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

using namespace std;

typedef pair<int, int> pr;
typedef vector<int> vec;
typedef long long int lli;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define TEST int T; cin >> T; while(T--)


int main() {
    int n;
    cin >> n;
    char str[n];
    cin >> str;

    int l=0, r=n-1, ans = 0;

    while(l<r) {
        while(l < n && str[l] == 'R') l++;
        while(r >= 0 && str[r] == 'W') r--;

        if(l>=r) break;
        
        // cout << l << r << endl;

        ans += 1;
        l++;
        r--; 
    }

    cout << ans << endl;
}

Measured memory_bytes: 3820
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;

int main(){
    int a[3];lol(i,3)cin>>a[i];
    sort(a,a+3);
    cout<<a[2]*10+a[1]+a[0]<<endl;
    return 0;
}


Measured memory_bytes: 256
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define Graph vector<vector<int>>
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1000000007;

// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// using Bint = mp::cpp_int;
// using Real = mp::number<mp::cpp_dec_float<1024>>;

int main(){
    ll N;
    cin >> N;
    map<ll, int> M;

    for(ll i = 2; i * i <= N; i++){
        while(N % i == 0){
            M[i]++;
            N /= i;
        }
    }

    if(N != 1) M[N]++;

    int ans = 0;


    for(auto i : M){
        // cout << i.first << ' ' << i.second << endl;
        int c = 1;
        while((c + 1) * (c + 2) / 2 <= i.second){
            c++;
        }
        ans += c;
    }

    cout << ans << endl;
}

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

using namespace std;
using ll = long long;

const long long INF = 1LL << 60;
const int MOD = 1000000007;

int n;
double dp[301][301][301] = {};

double rec(int i, int j, int k) {
    if (dp[i][j][k] >= 0.0) {
        return dp[i][j][k];
    }

    double res = 0.0;
    if (i > 0) res += rec(i-1, j, k) * i;
    if (j > 0) res += rec(i+1, j-1, k) * j;
    if (k > 0) res += rec(i, j+1, k-1) * k;

    res += n;
    res *= 1.0 / (double)(i + j + k);
    return dp[i][j][k] = res;
}

int main() {
    #ifdef MYLOCAL
        ifstream in("input.txt");
        cin.rdbuf(in.rdbuf());
    #endif

    cin >> n;

    int one = 0, two = 0, three = 0;
    for (int i = 0; i < n; ++i) {
        int a; cin >> a;
        if (a == 1) ++one;
        else if (a == 2) ++two;
        else ++three;
    }

    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= n; ++j){
            for(int k = 0; k <= n; ++k){
                dp[i][j][k] = -1.0;
            }
        }
    }

    dp[0][0][0] = 0.0;
    double ans = rec(one, two, three);

    cout << fixed << setprecision(10) << ans << endl;

    return 0;
}

Measured memory_bytes: 213376
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;
#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let s = read_as_string();
    let t = read_as_string();
    if t.starts_with(&s){
        println!("Yes");
    }else{
        println!("No");
    }
}


Measured memory_bytes: 2108
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define prArr(a) {cerr<<(#a)<<"={";int i=0;for(auto t:(a))cerr<<(i++?", ":"")<<t;cerr<<"}"<<endl;}
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE

vector<Int> A(3), B(3);

Int calc2(Int N){
  vector<Int> dp(N + 1);
  for(Int i=0;i<3;i++){
    for(Int j=0;j<=N;j++){
      if(j + 1 <= N) Max(dp[j+1], dp[j] + 1);
      if(j + B[i] <= N) Max(dp[j + B[i]], dp[j] + A[i]);
    }
  }
  return dp[N];
}

Int calc1(Int N){
  vector<Int> dp(N + 1);
  for(Int i=0;i<3;i++){
    for(Int j=0;j<=N;j++){
      if(j + 1 <= N) Max(dp[j+1], dp[j] + 1);
      if(j + A[i] <= N) Max(dp[j + A[i]], dp[j] + B[i]);
    }
  }
  return dp[N];
}

signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);
  Int N;
  cin>>N;
  cin>>A>>B;

  Int a = calc1(N);
  Int ans = calc2(a);
  cout<<ans<<endl;
  return 0;
}


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

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
fn main() {
    input! {
        n: i64,
        a: [i64; n],
    }
    if let Some(aj) = a.iter().max() {
        if let Some(ij) = a.iter().min() {
            println!("{}", aj - ij);
        }
    }
}

Measured memory_bytes: 4352
S = "".join(list(reversed(list(input()))))

flag = 0
while flag == 0 :
    if (S[0:7] == "remaerd") and (len(S) >= 7) :
        S = S[7:]
    elif (S[0:6] == "resare" and len(S) >= 6) :
        S = S[6:]
    elif ((S[0:5] == "maerd") or (S[0:5] == "esare")) and (len(S) >= 5) :
        S = S[5:]
    elif len(S) == 0 :
        ans = 1
        flag = 1
    else :
        ans = -1
        flag = 1
D = {1:"YES",-1:"NO"}
print(D[ans])


Measured memory_bytes: 4772
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 60;
long long dp[100010];
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;}
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
  bool s[15][15] = {false};
  int n, m, k, tmp;
  cin >> n >> m;
  int p[m];
  rep(i,m){
    cin >> k;
    rep(j,k){
      cin >> tmp;
      s[i][tmp-1] = true;
    }
  }
  rep(i,m)
    cin >> p[i];
  int ans = 0;
  rep(i,(1<<n)){
    bool flag = true;
    int bit[15];
    rep(j,n){
      bit[j] = (i/(1<<j)%2);
      //cout << bit[j];
    }
    //cout << endl;
    rep(j,m){
      int tmp = 0;
      rep(k,n){
        tmp += s[j][k]*bit[k];
      }
      if(tmp%2!=p[j])
        flag = false;
    }
    if(flag)
      ans++;
  }
  cout << ans << endl;
}


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

int main()
{
    long n;
    cin >> n;
    long a[n][3];
    for(long i=0;i<n;i++)
        for(long j=0;j<3;j++)
            cin >> a[i][j];

    long dp[n][3];
    for(long i=0;i<3;i++)
        dp[0][i] = a[0][i];

    for(long i=1;i<n;i++)
    {
        for(int j=0;j<3;j++)
        {
            long temp = j==0?max(dp[i-1][j+1],dp[i-1][j+2]):j==1?max(dp[i-1][j-1],dp[i-1][j+1]):max(dp[i-1][j-2],dp[i-1][j-1]);
            dp[i][j] = a[i][j] + temp;
            //cout << temp << "\n";
        }
    }
    long res = INT_MIN;



    for(int i=0;i<3;i++)
    {
        res = max(res,dp[n-1][i]);
        //cout << res << "\n";
    }

    cout << res << "\n";
}



Measured memory_bytes: 8332
#include<iostream>
#include<cstring>
#define DIM 200005
using namespace std;
//ifstream cin("date.in");
//ofstream cout("date.out");
int n, L, i, j, ok, k;
char s[DIM], a[DIM];
int p[DIM];
long long st, dr, fib[10000], sol[200], sn[200], sk[200];
void solve(int m, long long x, int semn){
    if(m <= 2){
        if(x <= n){
            for(int i = 1; i <= x; i++){
                sol[ s[i] ] += semn;
            }
        }
        else{
            for(int i = 1; i <= n; i++){
                sol[ s[i] ] += semn;
            }
            for(int i = 1; i <= x - n; i++){
                sol[ s[i] ] += semn;
            }
        }
        return;
    }
    if(fib[m - 1] * n + fib[m - 2] * k >= x){
        solve(m - 1, x, semn);
    }
    else{
        x -= fib[m - 1] * n + fib[m - 2] * k;
        for(int i = 'a'; i <= 'z'; i++){
            sol[i] += sn[i] * fib[m - 1] * semn;
            sol[i] += sk[i] * fib[m - 2] * semn;
        }
        solve(m - 2, x, semn);
    }
}
int main(){
    cin>> s + 1;
    n = strlen(s + 1);
    cin>> st >> dr;
    n /= 2;
    for(i = 2; i <= n; i++){
        while(L > 0 && s[i] != s[L + 1]){
            L = p[L];
        }
        if(s[i] == s[L + 1]){
            L++;
        }
        p[i] = L;
    }
    for(i = 1; i <= n; i++){
        ok = 1;
        for(j = i + i; j <= n; j += i){
            if(p[j] != j - i){
                ok = 0;
            }
        }
        L = 1;
        for(j = j - i + 1; j <= n; j++){
            if(s[j] != s[L]){
                ok = 0;
            }
            L++;
        }
        if(ok == 1){
            k = i;
            break;
        }
    }
    for(i = 1; i <= n; i++){
        sn[ s[i] ]++;
    }
    for(i = 1; i <= k; i++){
        sk[ s[i] ]++;
    }
    fib[1] = fib[2] = 1;
    for(i = 3; ; i++){
        fib[i] = fib[i - 1] + fib[i - 2];
        if(fib[i] * n >= dr || fib[i] * n + fib[i - 1] * k >= dr){
            solve(i, dr, 1);
            solve(i, st - 1, -1);
            break;
        }
    }
    for(i = 'a'; i <= 'z'; i++){
        cout<< sol[i] <<" ";
    }
}


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

ll floorx(ll a, ll b, ll x){
    return (a * x) / b + a * (x / b); 
}

int main(){
    ll A, B, N;
    cin >> A >> B >> N;
    cout << min(floorx(A, B, N), floorx(A, B, B-1));
	return 0;
}

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

int main(){
    int_fast64_t N;
    scanf("%lld", &N);
    vector<int_fast64_t> a(N), b(N), c(N), d(N);
    for(int i = 0; i < N; ++i)scanf("%lld", &a[i]);
    b[N - 1] = 0;
    {
        stack<int_fast64_t> stc;
        for(int_fast64_t i = N - 2; i >= 0; --i) {
            b[i] = b[i + 1];
            auto aa = a[i + 1], ab = a[i];
            while(aa < ab){
                int_fast64_t t = stc.empty() ? N - 1 : stc.top();
                b[i] += (t - i) * 2;
                if(!stc.empty()) stc.pop();
                aa *= 4;
            }
            while(aa >= ab * 4){
                stc.push(i);
                ab *= 4;
            }
        }
    }
    c[0] = 1;
    {
        stack<int_fast64_t> stc;
        for(int_fast64_t i = 1; i < N; ++i) {
            c[i] = c[i - 1] + 1;
            auto aa = a[i - 1], ab = a[i];
            while(aa < ab){
                int_fast64_t t = stc.empty() ? 0 : stc.top();
                c[i] += (i - t) * 2;
                if(!stc.empty()) stc.pop();
                aa *= 4;
            }
            while(aa >= ab * 4){
                stc.push(i);
                ab *= 4;
            }
        }
    }
    int_fast64_t ans(min(c[N - 1], b[0]));
    for(int i = 0; i < N - 1; ++i){
        ans = min(ans, c[i] + b[i + 1]);
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cout<<(#v)<<":";for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;
#define printVS(vs) cout<<(#vs)<<":"<<endl;for(auto(s):(vs)){cout<<(s)<< endl;}
#define printVV(vv) cout<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;}
#define printP(p) cout<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cout<<(#vp)<<":"<<endl;for(auto(p):(vp)){cout<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cout << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cout << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1e9;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

int n;
const int MAX = 1e6;
int a[MAX];

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

    int n;
    cin >> n;
    int l = 0;
    a[0] = 1;

    rep(q, n) {
        int x;
        cin >> x;

        if (x < l) {
            cout << "No" << endl;
            continue;
        }

        cout << "Yes" << endl;
        if (x >= MAX) continue;
        for (int i = x; l <= i; i--) {
            if (a[i] == 1) {
                a[i] = 0;
                for (int j = i + 1; j <= x; j++) {
                    a[j] = 1;
                }
                while (l < MAX && !a[l]) {
                    l++;
                }
                break;
            }
        }
    }
}

Measured memory_bytes: 10928
h, w, k = map(int, input().split())
s = [[None]*w for _ in range(h)]
ichigo = 0

for i in range(h):
    c = 0
    f = 0
    a = input()
    for j in range(w):
        if a[j] == '#':
            ichigo += 1
            c = ichigo
            if not f:
                f = c
        s[i][j] = c
    if f:
        for j in range(w):
            if s[i][j] == 0:
                s[i][j] = f
            else:
                break

for i in range(h-1):
    if s[i+1][0] == 0:
        for j in range(w):
            s[i+1][j] = s[i][j]

for i in range(h-1, -1, -1):
    if s[i-1][0] == 0:
        for j in range(w):
            s[i-1][j] = s[i][j]

for i in range(h):
    print(' '.join(map(str, s[i])))


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

int main(){
  int N = 0;
  cin >> N;
  int a[N];
  double average = 0;
  for(int i = 0; i < N; i++){
    cin >> a[i];
    average += a[i];
  }
  average = average / (double)N;
  double sum = 9999;
  int answer = 0;
  bool first = true;
  for(int i = 0; i < N; i++){
    double compare = (double)a[i] - average;
    if(compare < 0){
      compare *= -1;
    }
    if(compare == sum && first){
      cout << i << endl;
      return 0;
    }
    if(compare < sum){
      sum = compare;
      answer = i;
      first = false;
    }
  }
  cout << answer << endl;
  return 0;
}


Measured memory_bytes: 256