akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	int N,a,div,ans;
	vector<int> d;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a;
		d.push_back(a);
	}
	sort(d.begin(), d.end());
	div = N / 2;
	ans = d[div] - d[div - 1];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 892
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
using namespace std;

int main() {
	int N,M,a, b,MAX=-100,min=100,o=0;
	cin >> N >> M >> a >> b;
	vector<int>x(N),y(M);
	for(int i=0;i<N;i++){
		cin >> x[i];
		if (MAX < x[i])MAX = x[i];
	}
	for (int j = 0; j < M; j++) {
		cin >> y[j];
		if (min > y[j])min = y[j];
	}
	for (int l = a + 1; l <= b; l++) {
		if (MAX < l && l <= min)o++;
	}
	if (o > 0)cout << "No War" << endl;
	if (o == 0)cout << "War" << endl;
	return 0;
}

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

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

    int n;
    cin >> n;

    long long c[n];
    for (int i = 0; i < n; ++i) {
        cin >> c[i];
    }
    sort(c, c + n);

    int first_ix = 0;
    for (int i = 0; i < n - 1; ++i) {
        if (c[i] * 2 < c[i + 1]) first_ix = i + 1;
        c[i + 1] += c[i];
    }

    cout << n - first_ix << '\n';

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i, n) for(int i = n; i >= 0; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define SORT(v) sort((v).begin(), (v).end())
#define REV(v) sort((v).begin(), (v).end(), greater<int>())
#define INF 1000000007
typedef long long ll;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a * b / gcd(a, b);};
int month[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};


int main() {
  int n, q;
  cin >> n >> q;
  UnionFind u(n);
  rep(i, q) {
    int Q, a, b;
    cin >> Q >> a >> b;
    if(!Q) {
      u.unite(a, b);
    } else {
      if(u.same(a, b)) cout << 1 << endl;
      else cout << 0 << endl;
    }
  }
  return 0;
}



Measured memory_bytes: 3200
import itertools
N=int(input())

fmat=[]
for i in range(N):
  array=list(map(int,input().split()))
  fmat.append(array)
  
pmat=[]
for i in range(N):
  array=list(map(int,input().split()))
  pmat.append(array)
#print(fmat)
#print(pmat)

max_answer=-10**9
for bit in itertools.product(range(2),repeat=10):
  if sum(bit)==0:
    continue
    
  answer=0  
  for i in range(N):
    both_num=0
    for j in range(10):
      if bit[j]==1 and fmat[i][j]==1:
        both_num+=1
    
    answer+=pmat[i][both_num]
    
  max_answer=max(max_answer,answer)
  
print(max_answer)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1000000007;
const ll INF = 1061109567;
const double EPS = 1e-10;
int main(){
    int a,b;
    cin>>a>>b;
    int c=a+b;
    if(c%3==0||a%3==0||b%3==0){
        cout<<"Possible"<<endl;
    }else{
        cout<<"Impossible"<<endl;
    }

    return 0;
}


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

const int maxN = 3e5 + 100;

int a[maxN + 1], n, b[maxN + 1], tmp;

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]), tmp ^= a[i];
	if(tmp == 0) puts("Yes");
	else puts("No");
	return 0;
}

Measured memory_bytes: 512
#include<stdio.h>
int h[100000],n,m,i,j,p=0,g,r=0;
int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<n;h[i]+=h[i-1],i++)
		scanf("%d",&h[i]);
	
	for(;m--;)
	{
		scanf("%d",&g);
		if(g>0)
			r+=h[p+g]-h[p];
		else
			r+=h[p]-h[p+g];
		r%=100000;
		p+=g;
	}
	printf("%d\n",r);
	return 0;
}

Measured memory_bytes: 984
#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 rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#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(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  int n, k;
  cin >> n >> k;
  int ans = 1;
  rep(i, n){
    int a1 = ans * 2;
    int a2 = ans + k;
    ans = min(a1, a2);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3596
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
#include <random>

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

const int L=1e5+10;
char s[L];
char t[L];
int main() {
	int N;
	scanf("%d",&N);
	scanf("%s",s);
	s[N]=s[0];
	auto op="SW";
	for(int i=0;i<2;i++){
		t[0]=op[i];
		for(int j=0;j<2;j++){
			t[1]=op[j];
			for(int k=2;k<=N+1;k++){
				if((t[k-1]=='S'&&s[k-1]=='o')||
					(t[k-1]=='W'&&s[k-1]=='x')){
					t[k]=t[k-2];
				}
				else {
					t[k]=(t[k-2]=='S')?'W':'S';
				}
			}
			if(t[N]==t[0]&&t[N+1]==t[1]){
				t[N]=0;
				puts(t);
				return 0;
			}
		}
	}
	puts("-1");

	return 0;
}



Measured memory_bytes: 512
#include<bits/stdc++.h>
#define lg long long int
#define loop(i,s,e) for(lg i=s;i<=e;i++)
#define iloop(i,s,e) for(lg i=e;i>=s;i--)
#define pb push_back
#define mp make_pair
using namespace std;

lg min(lg a,lg b)
{return a<b?a:b;}
lg max(lg a,lg b)
{return a>b?a:b;}
lg lcm(lg a ,lg b)
{
    return (a*b)/__gcd(a,b);
}

lg ans,n,m,k;;
void sol(vector<vector<lg>>& gr,vector<lg> rows,vector<lg> cols,lg i,lg j,lg now)
{
    if(now<k)
    {
        return ;
    }
    if(i==n)
    {
        if(j==m)
        {
            if(now==k) ans++;
        }
        else
        {
            sol(gr,rows,cols,i,j+1,now);
            sol(gr,rows,cols,i,j+1,now-cols[j]);
        }
    }
    else
    {
        sol(gr,rows,cols,i+1,j,now);
        for(lg l=0;l<m;l++)
        {
            if(gr[i][l]==1) cols[l]--;
        }
        sol(gr,rows,cols,i+1,j,now-rows[i]);
    }
}

int main()
{
    ans=0;

    cin>>n>>m>>k;

    vector<vector<lg>>gr(n,vector<lg>(m,0));
    vector<lg>rows(n,0);
    vector<lg>cols(m,0);
    lg tot=0;
    for(lg i=0;i<n;i++)
    {
        for(lg j=0;j<m;j++)
        {
            char a;
            cin>>a;
            if(a==35)
            {
                cols[j]++;
                rows[i]++;
                gr[i][j]=1;
                tot++;
            }
        }
    }
    sol(gr,rows,cols,0,0,tot);
    cout<<ans<<endl;
}


Measured memory_bytes: 3508
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.StringBuilder
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val x = sc.nextLong()
    var ans = x / 11 * 2
    if (x % 11 > 0 && x % 11 <= 6) ans++
    else if (x % 11 > 0) ans += 2
    println(ans)
}

fun main(args: Array<String>) {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

class mint {
public:
    long long x;

    constexpr mint(long long x = 0) : x((x % MOD + MOD) % MOD) {}

    constexpr mint operator-() const {
        return mint(-x);
    }

    constexpr mint &operator+=(const mint &rhs) {
        if ((x += rhs.x) >= MOD) x -= MOD;
        return *this;
    }

    constexpr mint &operator-=(const mint &rhs) {
        if ((x += MOD - rhs.x) >= MOD) x -= MOD;
        return *this;
    }

    constexpr mint &operator*=(const mint &rhs) {
        (x *= rhs.x) %= MOD;
        return *this;
    }

    constexpr mint operator+(const mint &rhs) const {
        mint res(*this);
        return res += rhs;
    }

    constexpr mint operator-(const mint &rhs) const {
        mint res(*this);
        return res -= rhs;
    }

    constexpr mint operator*(const mint &rhs) const {
        mint res(*this);
        return res *= rhs;
    }

    [[nodiscard]] constexpr mint pow(long long t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    [[nodiscard]] constexpr mint inv() const {
        return pow(MOD - 2);
    }

    mint &operator/=(mint rhs) {
        return *this *= rhs.inv();
    }

    mint operator/(const mint rhs) const {
        return mint(*this) /= rhs;
    }

    constexpr bool operator==(const mint &rhs) const noexcept {
        return this->x == rhs.x;
    }

    constexpr bool operator!=(const mint &rhs) const noexcept {
        return this->x != rhs.x;
    }

    bool operator<(const mint &rhs) const noexcept {
        return this->x < rhs.x;
    }

    bool operator>(const mint &rhs) const noexcept {
        return this->x > rhs.x;
    }

    bool operator<=(const mint &rhs) const noexcept {
        return this->x <= rhs.x;
    }

    bool operator>=(const mint &rhs) const noexcept {
        return this->x >= rhs.x;
    }

    friend istream &operator>>(istream &is, mint &a) {
        long long t;
        is >> t;
        a = mint(t);
        return is;
    }

    friend ostream &operator<<(ostream &os, const mint &a) {
        return os << a.x;
    }
};


void solve() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    vector<ll> acc(N + 1, 0);
    rep(i, N) {
        acc[i + 1] = acc[i] + A[i];
    }
    mint ans = 0;
    rep(i, N) {
        ans += mint(A[i]) * (acc[N] - acc[i + 1]);
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


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

namespace ProblemB
{
    class Program
    {
        static void Main()
        {
            var buff = GetIntArray();

            int X = buff[0];
            int Y = buff[1];

            for(int i = 0; i <= X; i++)
            {
                if(Y == i * 2 + (X - i) * 4)
                {
                    Console.WriteLine("Yes");
                    return;
                }
            }
            Console.WriteLine("No");
        }

        //入力関係のメソッド
        public static int GetInt() => int.Parse(Console.ReadLine());
        public static int[] GetIntArray() => Console.ReadLine().Split().Select(int.Parse).ToArray();
        public static double GetDouble() => double.Parse(Console.ReadLine());
        public static double[] GetDoubleArray() => Console.ReadLine().Split().Select(double.Parse).ToArray();
        public static long GetLong() => long.Parse(Console.ReadLine());
        public static long[] GetLongArray() => Console.ReadLine().Split().Select(long.Parse).ToArray();
        //出力関係のメソッド
        public static void OutIntArray(int[] values)
        {
            foreach (var value in values)
            {
                Console.WriteLine(value);
            }
        }
        public static void OutLongArray(long[] values)
        {
            foreach (var value in values)
            {
                Console.WriteLine(value);
            }
        }
        public static void OutList(List<object> list)
        {
            foreach (var value in list)
            {
                Console.WriteLine(value);
            }
        }

    }
}


Measured memory_bytes: 28240
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 2010;
char s[SIZE][SIZE];
int dp[SIZE][SIZE],row[SIZE][SIZE],col[SIZE][SIZE];
int get(int x1,int y1,int x2,int y2){
    int res=0;
    x1--;
    res-=row[x1][y1]+row[x2][y2]-row[x1][y2]-row[x2][y1];
    x1++;y1--;
    res-=col[x1][y1]+col[x2][y2]-col[x1][y2]-col[x2][y1];
    x1--;
    res+=dp[x1][y1]+dp[x2][y2]-dp[x1][y2]-dp[x2][y1];
    return res;
}
int main(){
    DRIII(N,M,Q);
    REPP(i,1,N+1)RS(s[i]+1);
    REPP(i,1,N+1)REPP(j,1,M){
        if(s[i][j]=='1'&&s[i][j+1]=='1')row[i][j+1]=1;
    }
    REPP(i,1,N)REPP(j,1,M+1){
        if(s[i][j]=='1'&&s[i+1][j]=='1')col[i+1][j]=1;
    }
    REPP(i,1,N+1){
        REPP(j,1,M+1){
            dp[i][j]=dp[i][j-1]+(s[i][j]-'0');
            row[i][j]+=row[i][j-1];
            col[i][j]+=col[i][j-1];
        }
    }
    REPP(i,1,N+1){
        REPP(j,1,M+1){
            dp[i][j]+=dp[i-1][j];
            row[i][j]+=row[i-1][j];
            col[i][j]+=col[i-1][j];
        }
    }
    while(Q--){
        DRII(x1,y1);
        DRII(x2,y2);
        printf("%d\n",get(x1,y1,x2,y2));
    }
    return 0;
}


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

template<class c> auto try_out(c a) -> decltype(cerr << a, 0);
char try_out(...);

struct debug {
#ifdef LOCAL
template<class c, class d> debug& operator << (pair<c, d> e) {
	return *this << "(" << e.first << ", " << e.second << ")";
}
template<class c> typename enable_if<sizeof(try_out(declval<c>())) != 1, debug&>::type operator << (c a) {
	cerr << boolalpha << a;
	return *this;
}
template<class c> typename enable_if<sizeof(try_out(declval<c>())) == 1, debug&>::type operator << (c a) {
	*this << "[";
	for (auto it = a.begin(); it != a.end(); ++it)
		*this << ","[1 - (it != a.begin())] << *it;
	return *this << "]";
}
#else
template<class c> debug& operator << (c) {
	return *this;
}
#endif
};

#define aty(x) " [" << #x ": " << x << "] "

using ll = long long;






int main() {
	
    int n;
    cin >> n;
    if (n == 3 || n == 5 || n == 7) cout << "YES\n";
    else cout << "NO\n";
	
	
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);

		String N = sc.next();

		for (int i = 0; i < 3; i++) {
			if (N.charAt(i) == '1') {
				System.out.print(9);

			} else if (N.charAt(i) == '9') {
				System.out.print(1);
			} else {
				System.out.print(N.charAt(i));
			}
		}

	}

}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for (int (i) = 1; (i) <= (n); (i++))
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define yn {puts("Yes");}else {puts("No");}
#define printd(x) printf("%.12f\n", ans);
template<class T> bool chmin(T& a, const T& b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> bool chmax(T& a, const T& b) {if (a < b) {a = b; return 1;} return 0;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main(void) {
	int x, y, z;
	cin >> x >> y >> z;
	swap(x, y);
	swap(x, z);

	cout << x << " " << y << " " << z << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define SORT(i) sort((i).begin(), (i).end())
#define INF 2000000000
constexpr ll mod = 1e9 + 7;
 
int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> B(N);
    vector<int> C(N - 1);
    for (int i = 0; i < N;++i){
        int a;
        cin >> a;
        A[i] = a - 1;
    }
    for (int i = 0; i < N;++i){
        cin >> B[i];
    }
    for (int i = 0; i < N-1;++i){
        cin >> C[i];
    }
    int ans = 0;
    for (int i = 0; i < N;++i){
        int val = A[i];
        ans += B[val];
        if(i != 0){
            if(val - A[i-1] == 1){
                ans += C[val - 1];
            }
        }
    }
    cout << ans << "\n";

    return 0;
}

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

#define rep(x, n) for(int i = x; i < (n); ++i)

using namespace std;
using ll = long long;

int main(void)
{
  int a, b, c, k;
  cin >> a >> b >> c >> k;

  bool res = false;
  for(int i = 0; i < k; ++i) {
    if(a >= b) {
      b *= 2;
    } else if (b >= c) {
      c *= 2;
    }
    if (a < b && b < c) res = true;
  }

  cout << (res ? "Yes" : "No") << endl;
}

Measured memory_bytes: 3644
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int D = sc.nextInt();

		sc.close();
		
		String result = null;
		while (result == null) {
			C -= B;
			if (C <= 0) {
				result = "Yes";
				break;
			}
			A -= D;
			if (A <= 0) {
				result = "No";
			}
		}
		System.out.println(result);
	}
}

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

int main(){
  string A, B;
  cin>>A>>B;
  if(A==B) cout<<"EQUAL"<<endl;
  else if(A.size()>B.size()) cout<<"GREATER"<<endl;
  else if(A.size()<B.size()) cout<<"LESS"<<endl;
  else if(A.size()==B.size()){
    if(A>B) cout<<"GREATER"<<endl;
    if(A<B) cout<<"LESS"<<endl;
  }
}


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

using namespace std;

#define ll long long
#define pii pair<int, int>
#define MAX 105

ll dp[MAX][100005];
ll W[MAX], V[MAX];
ll n, w;

ll INF = 1e14;

int main() {

    cin >> n >> w;

    for(int i = 1; i <= n; i++) {
        cin >> W[i] >> V[i];
    }


    for(int i = 1; i < 100005; i++) {
        dp[0][i] = INF;
    }


    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        for(ll j = 1; j < 100005; j++) {
            if(j - V[i] >= 0) {
                dp[i][j] = min(dp[i - 1][j - V[i]] + W[i], dp[i - 1][j]);

            }
            else dp[i][j] = dp[i - 1][j];
            if(dp[i][j] != INF && dp[i][j] <= w) ans = max(ans, j);
        }

    }
    cout << ans << '\n';


    return 0;
}


Measured memory_bytes: 80256
s = int(input())

def f(n):
  if n%2==0:
    return n//2
  else:
    return 3*n+1
  
r = [s]
n = s
c = 1
while True:
  n = f(n)
  c += 1
  if n in r:
    break
  r.append(n)
print(c)

Measured memory_bytes: 2940
#include <iostream>
using namespace std;
int h,w,x[4]={0,-1,0,1},y[4]={-1,0,1,0};
char s[50][50];
bool ok;
int main(){
    cin>>h>>w;
    for(int i=0;i<h;i++)for(int j=0;j<w;j++)cin>>s[i][j];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j]=='.')continue;
            ok=false;
            for(int k=0;k<4;k++){
                int ni=i+x[k],nj=j+y[k];
                if(ni<0||h<=ni||nj<0||w<=nj) continue;
                if(s[ni][nj]=='#') ok=true;
            }
            if(!ok){
                cout<<"No"<<endl;
                return 0;
            }
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}

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

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::swap;
using std::string;

class card {
	public:
		card(string s) {
			suit = s[0];
			num = s[1];
		}
		char suit;
		char num;
		bool operator<(const card& e) const {
			if(num == e.num) return suit < e.suit;
			return num < e.num;
		}
		bool operator==(const card& e) const {
			return suit == e.suit && num == e.num;
		}
		bool operator!=(const card& e) const {
			return suit != e.suit || num != e.num;
		}
};

vector<card> bubble,selection;

int main(void) {
	string s;
	int n;
	cin >> n;
	for(int i = 0;i < n;i++) {
		cin >> s;
		bubble.push_back(card(s));
		selection.push_back(card(s));
	}
	for(int i = 0;i < n;i++) {
		for(int j = n-1;j > i;j--){
			if(bubble[j].num < bubble[j-1].num)
				swap(bubble[j],bubble[j-1]);
		}
	}
	for(int i = 0;i < n;i++) {
		int minj = i;
		for(int j = i;j < n;j++) {
			if(selection[j].num < selection[minj].num)
				minj = j;
		}
		swap(selection[minj],selection[i]);
	}
	bool sstable = true;
	for(int i = 0;i < n;i++) {
		if(selection[i] != bubble[i]) sstable = false;
	}
	for(int i = 0;i < n-1;i++) cout << bubble[i].suit << bubble[i].num << " ";
	cout << bubble[n-1].suit << bubble[n-1].num << endl << "Stable" << endl;
	for(int i = 0;i < n-1;i++) cout << selection[i].suit << selection[i].num << " ";
	cout << selection[n-1].suit << selection[n-1].num << endl;
	if(sstable) cout << "Stable" << endl;
	else cout << "Not stable" << endl;
}




Measured memory_bytes: 3196
#include <bits/stdc++.h>
  
using namespace std;
#define forn(i, n) for (int i = 0; i < n; i++)
#define re return
#define fi first
#define mp make_pair
#define se second
#define sz(a) (int)a.size()
#define prev previ
#define tm tmmm
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

int n;
vector<int> a;
vector<int> p;
int main() {
   iostream::sync_with_stdio(0);
   //freopen("a.in", "r", stdin);
   cin >> n;
   a.resize(n);
   int ans = 0;
   forn (i, n) {
   		cin >> a[i];
   		if (sz(p) == 0) {
   			p.push_back(a[i]);
   			continue;
   		}
   		if (a[i] == p[sz(p) - 1]) continue;
   		if (sz(p) >= 2 && (p[0] < p[1] && p[sz(p) - 1] > a[i])) {
   			ans++;
   			p.resize(0);
   			p.push_back(a[i]);
   			continue;
   		}
   		if (sz(p) >= 2 && (p[0] > p[1] && p[sz(p) - 1] < a[i])) {
   			ans++;
   			p.resize(0);
   			p.push_back(a[i]);
   			continue;
   		}
   		p.push_back(a[i]);
   }
   if (sz(p)) ans++;
   cout << ans;
}



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

int main()
{
	int n;
	cin >> n;
	int ans;
	if(n < 10){
		ans = n;
	}else if(n < 100){
		int juunokurai = n /10;
		if(n > juunokurai * 11){
			ans = (juunokurai + 1) * 11;
		}else{
			ans = juunokurai * 11;
		}
	}else{
		int hyakunokurai = n / 100;
		if(n > hyakunokurai * 111){
			ans = (hyakunokurai + 1) * 111;
		}else{
			ans = hyakunokurai * 111;
		}
	}

	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 256
N,K = [int(i) for i in input().split()]

weight = 1
ans = 1
N -= 1

while N > 0:
    d = 0
    if weight % K == 0:
        d = weight // K
    else:
        d = weight // K + 1
    
    N -= d
    weight += d
    
    if N >= 0:
        ans += 1
        
print(ans)



Measured memory_bytes: 5604
#include<iostream>
#include<string>
using namespace std;
int keta(int n)
{
    int a=0;
    while(n>0){
        a=a+n%10;
        n/=10;
    }
    return a;
}
int main()
{
    int N,A,B,i,ans=0;
    cin>>N>>A>>B;
    for(i=1;i<=N;i++){
        if(A<=keta(i)&&keta(i)<=B)
        ans+=i;
    }    
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fto(i,a,b) for(int i=a; i<=b; ++i)
#define fdto(i,a,b) for(int i=a; i>=b; --i)
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define st first
#define nd second
#define maxn 200005
#define Ntu ""

using namespace std;
const int base = 1e9+7;
int n;
char s[maxn];
ll d[maxn], r[maxn];
int main()
{
    ios_base::sync_with_stdio(0);
    //freopen(Ntu".inp","r",stdin);
    //freopen(Ntu".out","w",stdout);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n;
    fto(i,1,n*2) cin >> s[i];
    fto(i,1,n*2)
    {
		d[i]=d[i-1];
		if(s[i]==s[i-1]) d[i] ^= 1;
	}
	fdto(i,n*2,1)
	{
		if(d[i]==1) r[i]=r[i+1]+1;
		else r[i]=r[i+1]-1;
	}
	ll rs = 1;
	fto(i,1,n*2) if(r[i] < 0)
    {
        rs = 0;
        break;
    }
	if(r[1] != 0 || s[1] == 'W') rs = 0;
	fto(i,1,n*2) if(!d[i]) rs = 1ll*rs*(r[i]+1)%base;
	fto(i,1,n) rs = rs*i%base;
	cout << rs;
    return 0;
}


Measured memory_bytes: 3584
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;

int main() {
	int N;
	string s,t;
	cin >> N >> s >> t;
	for(int i=0;i<=s.size();i++){
		if(s.substr(i)==t.substr(0,N-i)){
			cout << i+N << endl;
			return 0;
		}
	}
}


Measured memory_bytes: 256
//By Don4ick 
//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define forn(i, n) for (int i = 1; i <= n; i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define y1 qewr1234

const double PI = acos(-1.0);
const int DIR = 4;
const int X[] = {1, 0, -1, 0};
const int Y[] = {0, 1, 0, -1};

using namespace std;

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

	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);

	string s;
	map < char, bool > was;
	cin >> s;
	for (int i = 0; i < (int)s.size(); i++)
	{
		was[s[i]] = true;
	}
	if (was['N'] == was['S'] && was['W'] == was['E'])
	{	
		cout << "Yes" << endl;
	}
	else
		cout << "No" << endl;

	return 0;
}



Measured memory_bytes: 256
from collections import deque
from sys import stdin
n = int(input())
ddl = deque()
for i in stdin:
    inp = i.split()
    if len(inp) == 2:
        op, data = inp
        data = int(data)
    else: op, data = inp[0], None
    if op == 'insert':
        ddl.appendleft(data,)
    elif op == 'delete':
        try:
            ddl.remove(data)
        except ValueError:
            pass
    elif op == 'deleteFirst':
        ddl.popleft()
    elif op == 'deleteLast':
        ddl.pop()

print(' '.join([str(item) for item in ddl]))

Measured memory_bytes: 47948
#include <stdio.h>
#include <stdlib.h>
typedef long long ll;
ll min(ll x, ll y) {
	return x < y ? x : y;
}
int main() {
	int n, q, h, s, d;
	ll ans = 0;
	scanf("%d%d%d%d", &q, &h, &s, &d);
	scanf("%d", &n);
	s = min(4 * q, min(2 * h, s));
	ans = min((ll)n * s, (ll)n / 2 * d + (n % 2) * s);
	printf("%lld\n", ans);
	return 0;
}

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

int main() {
	static long long a[100000], b[100000], c[100000];
	static bool change[100000];
	int n;
	int start, end;
	int count;
	bool check = true;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
		c[i] = a[i] - b[i];
		change[i] = false;
	}

	sort(c, c + n);
	start = 0;
	end = n - 1;

	while (1) {
		if ((start == end && c[start] < 0) || c[end] < 0) {
			check = false;
			break;
		}
		if (c[start] >= 0) { 
			break; 
		}

		if (c[end] + c[start] == 0) {
			c[end] = 0;
			c[start] = 0;
			change[end] = true;
			change[start] = true;
			start++;
			end--;
		}
		else if (c[end] + c[start] > 0) {
			c[end] += c[start];
			c[start] = 0;
			change[end] = true;
			change[start] = true;
			start++;
		}
		else {
			c[start] += c[end];
			c[end] = 0;
			change[end] = true;
			change[start] = true;
			end--;
		}

	}

	count = 0;
	for (int i = 0; i < n; i++) {
		if (change[i]) {
			count++;
		}
	}

	if (check) {
		cout << count << endl;
	}
	else {
		cout << "-1" << endl;
	}
}

Measured memory_bytes: 2688
def main():
    questions = int(input())
    difficulty = sorted(list(map(int, input().split())))
    problems = int(input())
    problem_set = sorted(list(map(int, input().split())))
    d_index = 0
    count = 0
    for i in range(problems):
        while d_index < questions and difficulty[d_index] < problem_set[i]:
            d_index += 1
        if difficulty[d_index] == problem_set[i]:
            count += 1
            d_index += 1
        else:
            break
    print("YES" if count == problems else "NO")


if __name__ == '__main__':
    main()



Measured memory_bytes: 35428
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            new ABC128().SolveB(new ConsoleInput(Console.In, ' '));
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
  class ABC128
  {
    public void SolveB(ConsoleInput cin)
        {
            var n = cin.ReadInt;
            var S = new String[n];
            var P = new int[n];
            for (int i = 0; i < n; i++)
            {
                S[i] = cin.Read;
                P[i] = cin.ReadInt;
            }
            var setList = new List<GuideBook>();
            for (int i = 0; i < n; i++)
            {
                setList.Add(new GuideBook(i+1, S[i], P[i]));
            }
      var newList = setList.OrderBy(x => x.Name).ThenByDescending(x => x.Point);
            foreach (GuideBook set in newList)
            {
                WriteLine(set.No);
            }
            ReadLine();
        }
  }
  public class GuideBook
    {
        public int No { get; set; }
        public String Name { get; set; }
        public int Point { get; set; }
        public GuideBook(int no, String name, int point)
        {
            No = no;
            Name = name;
            Point = point;
        }
    }
}


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

const int _ = 2e5 + 7;
struct Edge{int end , upEd;}Ed[_ << 1];
int head[_] , cntEd , col[2] , N;
void addEd(int a , int b){Ed[++cntEd] = (Edge){b , head[a]}; head[a] = cntEd;}

void dfs(int x , int p , int c){
	++col[c];
	for(int i = head[x] ; i ; i = Ed[i].upEd)
		if(Ed[i].end != p) dfs(Ed[i].end , x , c ^ 1);
}

vector < int > pot[3]; int arr[_];
void dfs1(int x , int p , int c , int id){
	if(id == 2){
		int i = pot[c + 1].size() ? c + 1 : 0;
		arr[x] = pot[i].back(); pot[i].pop_back();
	}
	else
		if(!(id ^ c)){arr[x] = pot[0].back(); pot[0].pop_back();}
		else{
			int p = pot[1].empty() ? (pot[2].empty() ? 0 : 2) : 1;
			arr[x] = pot[p].back(); pot[p].pop_back();
		}
	for(int i = head[x] ; i ; i = Ed[i].upEd)
		if(Ed[i].end != p) dfs1(Ed[i].end , x , c ^ 1 , id);
}

signed main(){
	cin >> N;
	for(int i = 1 ; i < N ; ++i){int x , y; cin >> x >> y; addEd(x , y); addEd(y , x);}
	for(int i = 1 ; i <= N ; ++i) pot[i % 3].push_back(i);
	dfs(1 , 0 , 0); dfs1(1 , 0 , 0 , col[0] < pot[1].size() ? 0 : (col[1] < pot[2].size() ? 1 : 2));
	for(int i = 1 ; i <= N ; ++i) cout << arr[i] << ' ';
	return 0;
}


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

int main()
{
  int N, x;
  cin >> N >> x;
  
  vector<int> a;
  rep(i, N)
  {
    int tmp;
    cin >> tmp;
    a.push_back(tmp);
  }
  
  sort(a.begin(), a.end());
  
  int counter = 0;
  rep(i, N)
  {
    x -= a[i];
    
    if (0 <= x)
    {
      counter++;
    }
    else
    {
      break;
    }
  }
  
  if ((N == counter) && (0 < x))
  {
	  cout << counter - 1 << endl;
  }
  else
  {
    cout << counter << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(a,n) for (ll a = 0; a < (n); ++a)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
typedef vector<vector<ll> > Graph;
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; }
const ll INF = 1e18;

int main(){
    ll a;
    cin >> a;
    ll ans = a+a*a+a*a*a;
    cout << ans << endl;

    return 0;
}


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


typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;
int main(){
	int N;
	vector<pair<int,int>> tasks;
	cin>>N;
	for(int i=0;i<N;i++){
		int a,b;
		cin>>a>>b;
		tasks.emplace_back(b,a);
	}
	sort(tasks.begin(),tasks.end());
	int sum=0;
	for(auto v:tasks){
		sum+=v.second;
		if(sum>v.first){
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 3444
#include <stdio.h>
 
int main(void){
  int i,sum;
  char num[1001];
 
  for(;;){
    scanf("%s", &num);
    if(num[0] == '0') break;
     
    sum = 0;
    for(i=0;num[i]!='\0';i++)
      sum += num[i] - '0';
    printf("%d\n", sum);
  }
   
  return 0;
}


Measured memory_bytes: 2032
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl "\n"
#define rep(i,n) for(ll i=0; i<(n); i++)
typedef vector<ll> vl;
typedef vector<string> vs;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sortup(V) sort(V.begin(), V.end())
#define sortdown(V) sort(V.rbegin(), V.rend())
#define MOD 998244353 //1000000007

ll f(ll n) {
    if(n%2) return 3*n+1;
    else return n/2;
}

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

    // solution comes here
    ll s, ans=1;
    cin >> s;
    while(1) {
        if(s==4) {
            cout << ans + 3 << nl;
            return 0;
        }
        if(s==2) {
            cout << ans+3 << nl;
            return 0;
        }
        if(s==1) {
            cout << ans+3 << nl;
            return 0;
        }
        s = f(s);
        ++ans;
    }
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		long n = sc.nextLong();
		int res = Integer.MAX_VALUE;
		
		for (long i = 1; i <= (long)Math.sqrt(n*1.0); i++) {
			if (n % i == 0) {
				res = Math.min(res, F(i, n/i));
			} 
		}
		
		System.out.println(res);
	}
  
	private static int F(long a, long b) {
		return Math.max(findDigit(a), findDigit(b));
	}
	
	private static int findDigit(long num) {
		int n = 0;
		while (num != 0) {
			n++;
			num /= 10;
		}
		return n;
	}
	
    static class FastReader {
	    BufferedReader br;
	    StringTokenizer st;
	
	    public FastReader() {
	      br = new BufferedReader(new InputStreamReader(System.in));
	    }
	  
	    String next() { 
	      while (st == null || !st.hasMoreElements()) {
	        try {
	          st = new StringTokenizer(br.readLine());
	        } catch (IOException  e) {
	          e.printStackTrace();
	        }
	      }
	      return st.nextToken();
	    }
	
	    int nextInt() {
	      return Integer.parseInt(next());
	    }
	
	    long nextLong() {
	      return Long.parseLong(next());
	    }
	
	    double nextDouble() { 
	      return Double.parseDouble(next());
	    }
	
	    String nextLine() {
	      String str = "";
	        try{
	            str = br.readLine();
	        } catch (IOException e) {
	            e.printStackTrace();
	        }
	        return str;
	      }
	  }
}


Measured memory_bytes: 23252
#include <iostream>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(void){
    int n; cin >> n;
    int a[200001];
    for(int i=1;i<=n;i++) cin >> a[i];
    int target = 1;
    int score = 0;
    for(int i=1;i<=n;i++){
        if(a[i]!=target){
            score++;
        }else{
            target++;
        }
    }
    if(score==n)
        cout << -1 << endl;
    else
        cout << score << endl;
}



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


#define li			long long int
#define rep(i,to)	for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)	for(li i=(li)(start);i<((li)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)		idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)	for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)		idp p2((x).F, (x).S)
#define dump(x,n)	idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)	idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)	idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)	idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)	rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)	rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;

li a[200200];
PI aa[200200];
set<li> wall;

int main() {
	li n;
	cin >> n;
	rin{
		cin >> a[i];
		aa[i] = {a[i], i};
	}
	sort(aa, aa + n);
	li res = 0;
	wall.insert(-1);
	wall.insert(n);
	rep(i, n) {
		//p2p(aa[i]);
		//dumpi(wall);
		//cout << res << endl;
		set<li>::iterator r = wall.upper_bound(aa[i].S);
		set<li>::iterator l = r;
		l--;
		li ll = *l + 1;
		li rr = *r - 1;
		//p2(ll, rr);
		res += aa[i].F * (aa[i].S - ll + 1) * (rr - aa[i].S + 1);
		wall.insert(aa[i].S);
	}
	cout << res << endl;


	return 0;
}

Measured memory_bytes: 14336
while True:
	a,b=map(int,input().split())
	if a==0 and b==0:
		break
	o=0		
	for i in range(1,a-1):
		for j in range(i+1,a):
			for k in range(j+1,a+1):
				if i+j+k==b:
					o+=1
	print(o)	


Measured memory_bytes: 5596
while True:
    m,f,r = map(int,input().split())
    score = ""
    if(m == -1 and f == -1 and r == -1): break
    if(m == -1 or f == -1): score = "F"
    elif(m+f >= 80): score = "A"
    elif(m+f >= 65): score = "B"
    elif(m+f >= 50): score = "C"
    elif(m+f >= 30):
        if(r >= 50): score = "C"
        else: score = "D"
    else:
        score = "F"
    print(score)
    


Measured memory_bytes: 5596
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int n, m;
int main() {
	vector<string> ans;int field[21][21];
	while (cin >> n, n) {
		for (int i = 0; i < 21; ++i) {
			for (int j = 0; j < 21; ++j) {
				field[i][j] = 0;
			}
		}
		for (int i = 0; i < n; ++i) {
			int x, y; cin >> x >> y;
			field[y][x] = 1;
		}
		int x = 10, y = 10;
		int cnt = 0;
		cin >> m;
		for (int i = 0; i < m; ++i) {
			char dir;
			int step;
			cin >> dir >> step;
			while (step--) {
				switch (dir) {
				case'N': y++; break;
				case'S': y--; break;
				case'E': x++; break;
				default:x--; break;
				}
				if (field[y][x]) {
					field[y][x] = 0;
					cnt++;
				}
			}
		}
		ans.push_back((cnt == n) ? "Yes" : "No");
	}
	for (int i = 0; i < ans.size(); ++i) {
		cout << ans[i] << endl;
	}

	return 0;
}
	


Measured memory_bytes: 3160
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<ll,ll> P;

class RMQ{
public:
  int n;
  P dat[555555];
  void init(int _n){
    n=1;
    while(n<_n)n*=2;
    rep(i,2*n) dat[i]=P(MAX,-1);
  }
  void update(int k,P a){
    k+=n-1;dat[k]=a;
    while(k>0){
      k=(k-1)/2;
      dat[k]=min(dat[k*2+1],dat[k*2+2]);
    }
  }
  P query(int a,int b){return query(a,b,0,0,n);}
  P query(int a,int b,int k,int l,int r){
    if(r<=a||b<=l) return P(MAX,-1);
    if(a<=l&&r<=b) return dat[k];
    P vl=query(a,b,k*2+1,l,(l+r)/2);
    P vr=query(a,b,k*2+2,(l+r)/2,r);
    return min(vl,vr);
  }
};

class RMQ2{
public:
  int n;
  P dat[555555];
  void init(int _n){
    n=1;
    while(n<_n)n*=2;
    rep(i,2*n) dat[i]=P(-MAX,-1);
  }
  void update(int k,P a){
    k+=n-1;dat[k]=a;
    while(k>0){
      k=(k-1)/2;
      dat[k]=max(dat[k*2+1],dat[k*2+2]);
    }
  }
  P query(int a,int b){return query(a,b,0,0,n);}
  P query(int a,int b,int k,int l,int r){
    if(r<=a||b<=l) return P(-MAX,-1);
    if(a<=l&&r<=b) return dat[k];
    P vl=query(a,b,k*2+1,l,(l+r)/2);
    P vr=query(a,b,k*2+2,(l+r)/2,r);
    return max(vl,vr);
  }
};

RMQ t;
RMQ2 r;
ll n;

P calc(ll x) {
  P p=r.query(0,x);
  if(p.F==-MAX) p.S=-1;
  P q=r.query(0,p.S);
  if(q.F==-MAX) q.S=-1;
  return P(p.S,q.S);
}
P calc2(ll x) {
  P p=t.query(x+1,n);
  if(p.F==MAX) p.S=n;
  P q=t.query(p.S+1,n);
  if(q.F==MAX) q.S=n;
  return P(p.S,q.S);
}

void Main() {
  R n;
  P a[n];
  rep(i,n) {
    R a[i].F;
    a[i].S=i;
  }
  sort(a,a+n,greater<P>());
  t.init(n);
  r.init(n);
  ll ans=0;
  rep(i,n) {
    P p=calc(a[i].S);
    P q=calc2(a[i].S);
    ans+=abs(a[i].S-p.F)*abs(q.F-q.S)*a[i].F;
    ans+=abs(a[i].S-q.F)*abs(p.F-p.S)*a[i].F;
    t.update(a[i].S,P(0,a[i].S));
    r.update(a[i].S,P(0,a[i].S));
  }
  pr(ans);
}

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


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

typedef pair<long long, int> P;

long long pow5(long long x) {
    long long res = 1;
    int n = 5;
    while (n) {
        if (n & 1) res = res * x;
        x = x * x;
        n >>= 1;
    }
    return res;
}

int main() {
    int X;  cin >> X;
    deque<P> q;
    q.push_back(P(0, 0));
    long long current = 1;
    int n = 1;
    while (true) {
        if (current > 1e11) break;
        q.push_back(P(current, n));
        q.push_front(P(-current, -n));
        ++n;
        current = pow5(n);
    }
    auto left = q.begin(), right = q.begin();
    while (true) {
        while (right->first - left->first < X) {
            ++right;
        }
        if (right->first - left->first == X) {
            cout << right->second << " " << left->second << endl;
            return 0;
        }
        else if (right->first - left->first > X) {
            ++left;
        }
    }
}


Measured memory_bytes: 3636
#include<stdio.h>
#include<ctype.h>

int main(){
    int n,k;
    char s[50];

    scanf("%d %d",&n,&k);
    scanf("%s",s);

    if(k==0)
        s[0] = tolower(s[0]);
    else
        s[k-1] = tolower(s[k-1]);      

    printf("%s\n",s);

    return 0;  

}

Measured memory_bytes: 128
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int maxn=1e5+10;

int n,mx,f;
int z[maxn],x[maxn];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&z[i]),mx=max(mx,z[i]);

    for(int i=1;i<=n;i++)
        x[i]=min(z[i],mx-z[i]);

    sort(x+1,x+1+n);
    for(int i=1;i<=n;i++)
        if(z[i]==x[n]){f=1;break;}
    if(!f)x[n]=mx-x[n];
    printf("%d %d",mx,x[n]);

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using ll = long long;
using namespace std;
const long long INF = 1LL << 60;
ll mod = 1e9 + 7;

int main()
{
    string s, t;
    cin >> s >> t;
    bool ans = true;
    rep(i, s.size())
    {
        if (s[i] != t[i])
            ans = false;
    }
    cout << (ans ? "Yes" : "No") << endl;

    return 0;
}


Measured memory_bytes: 3624
n=int(input())
T,a=map(int,input().split())
h=list(map(int,input().split()))
t=abs(T-h[0]*0.006-a)
ans=1
for i in range(1,n):
    tmp=abs(T-h[i]*0.006-a)
    if tmp<t:
        ans=i+1
        t=tmp
print(ans)

Measured memory_bytes: 3064