akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define db(a) cout << fixed << #a << " = " << a << endl;

using namespace std;

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int A, B;
	cin >> A >> B;
	cout << A*B << endl;
}



Measured memory_bytes: 3652
import java.math.BigDecimal;
import java.util.*;

public class Main {

    Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        new Main().run();
    }

    void run() {

        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for (int i=0; i<n; i++) arr[i] = sc.nextInt();

        for (int i=0; i<Math.min(k, 100); i++) {
            int[] tmp = new int[n];
            for (int j=0; j<n; j++) {
                int l = Math.max(0, j-arr[j]);
                int r = Math.min(n-1, j+arr[j]);
                tmp[l]++;
                if (r+1<n) tmp[r+1]--;
            }
//            for (int j=0; j<n; j++) System.out.println(tmp[j]);
            for (int j=0; j<n-1; j++) {
                tmp[j+1] += tmp[j];
            }
            arr = tmp;
        }

        StringBuilder sb = new StringBuilder();

        for (int i=0; i<n; i++) sb.append(arr[i] + " ");

        System.out.println(sb.toString());

    }
}


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

#define ll long long
#define endl "\n"
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define f first
#define s second
#define vecll vector<ll>
#define pairll pair<ll,ll>
#define vecpairll vector<pair<ll,ll>>
#define mapllll map<ll,ll>
#define mapstrll map<string,ll>
#define mapllvecll map<ll,vecll>
#define setll set<ll>
#define fio ios_base::sync_with_stdio (false); cin.tie (NULL); cout.tie(NULL);

using namespace std;

ll const N=1e5+5;
ll const inf=1e18+5;
ll const MOD=1e9+7;

ll t,n,m,x,y,z,w,k;

int main()
{
    fio

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

    ll p = 1;
    for(ll i=0;i<n;i++)
    {
        if(a[i] == p)   p++;
    }

    p--;

    if((n-p) == n)
    {
        cout<<-1;
        return 0;
    }

    cout<<(n-p);

    return 0;
}



Measured memory_bytes: 1920
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)
















int main(){
    string s;
    cin >> s;
    bool f = true;
    REP(i, s.size()){
        if(i % 2 == 0){
            if(s[i] != 'h') f = false;
        }
        else{
            if(s[i] != 'i') f = false;
        }
    }
    if(f && s.size() % 2 == 0){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var kn = Console.ReadLine().Split(' ');
            // 演習の長さ
            var k = long.Parse(kn[0]);
            // 家の数
            var n = long.Parse(kn[1]);
            // 家の距離
            var a = Console.ReadLine().Split(' ');

            var max = 0L;

            for (var i = 1; i < n; i++)
            {
                max = Math.Max(long.Parse(a[i]) - long.Parse(a[i - 1]), max);
            }

            max = Math.Max(long.Parse(a[0]) + k - long.Parse(a[n - 1]), max);

            Console.WriteLine(k - max);
        }
    }
}

Measured memory_bytes: 30428
#include <iostream>
#include <algorithm>
#include <array>
#include <cstdint>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <vector>

#define INF 1000000000
#define MOD 1000000007
#define ll long long
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define bitget(a,b) (((a) >> (b)) & 1)
#define vint vector<int>
#define ALL(x) (x).begin(),(x).end()
#define C(x) cout << #x << " : " << x << endl
#define scanf scanf_s

using int32 = int_fast32_t;
using int64 = int_fast64_t;
using uint32 = uint_fast32_t;
using uint64 = uint_fast64_t;

using namespace std;

class UnionFind {
public:
	std::vector<int32> tree;
	//?????????????????????
	UnionFind(size_t size) :tree(size, -1) {}
	//x?????£??¨?????????
	int32 find(int32 x) {
		if (tree[x] < 0) return x;
		return tree[x] = find(tree[x]);
	}
	//x,y???????´??????????2???????????????
	void unite(int32 x, int32 y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (tree[x] > tree[y]) {
			tree[y] += tree[x];
			tree[x] = y;
		}
		else {
			tree[x] += tree[y];
			tree[y] = x;
		}
		return;
	}
	//x???????´???????????????????????´???°
	size_t size(int32 x) {
		return -tree[find(x)];
	}
	//x,y???????????????????±????????????????
	bool same(int32 x, int32 y) {
		return find(x) == find(y);
	}
};

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int32 n, q;
	cin >> n >> q;
	UnionFind t(n);
	bool c;
	int32 x, y;
	rep(i, 0, q) {
		cin >> c >> x >> y;
		if (c) {
			printf("%d\n", t.same(x, y));
		}
		else {
			t.unite(x, y);
		}
	}
	return 0;
}

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

#define rep(i,c) for(int i = 0; i < (int)c; ++i)
using llint = long long int ;
using namespace std;



int main(){
    int N;
    map<llint,llint> mp;
    int A[200006];
    cin>>N;
    rep(i,N){
        cin>>A[i];
        mp[A[i]]++;
    }

    llint num=0;
    for (auto itr = mp.begin(); itr != mp.end(); itr++)
    {
        llint seco=itr->second;
        if (seco==0) continue;
        else num+=seco*(seco-1)/2;
    }
    
    for (int i = 0; i < N; i++)
    {
        if (mp[A[i]]<2) cout<<num<<endl;
        else cout<<num-mp[A[i]]+1<<endl;
    }
    
    return 0;
}

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

int main()
{
	long long n, ans,a;
	a = 0;
	cin >> n;
	long long* k = new long long[n];
	for (long long i = 0; i < n; i++)
	{
		cin >> k[i];
	}

	sort(k, k + n, greater<int>());
	
	if (n % 2 == 0 )
	{
		for (long long p = 0; p < n / 2; p++)
		{
			a += 2 * k[p];
		}
		ans = a - k[0];
	}
	else
	{
		for (long long q = 0; q < (n + 1) / 2; q++)
		{
			a += 2 * k[q];
		}
		ans = a - k[0] - k[(n - 1) / 2];
	}

	cout << ans;

	delete[] k;
	return 0;
}

Measured memory_bytes: 4776
def solve():
    MOD = 10 ** 9 + 7
    N, K = map(int,input().split())
    mn = sum(list(range(K)))
    mx = sum(list(range(N,N-K,-1)))

    cnt = 0
    for i in range(K,N+2):
        if i != K:
            mn += i-1 % MOD
            mx += N-(i-1) % MOD
        cnt += mx % MOD - mn % MOD + 1 % MOD

    print(cnt % MOD)

if __name__ == '__main__':
    solve()

Measured memory_bytes: 66624
#include<bits/stdc++.h>
using namespace std;
int main() {
    string s, t;
    cin >> s;
    cin >> t;
    int sum=0;
    for(int i=0;i<s.length();++i) {
        if(s[i]==t[i]) ++sum;
    }
    cout << sum << endl;
}


                   
           


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cstdio>
#include<cmath>
#include<deque>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#include<tuple>
#include<utility>
#include<vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef vector<vector<int>> vvi;

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define REP(i, n)  for(int i=0; i<(int)(n); i++)
#define REPS(i, n)  for(int i=1; i<=(int)(n); i++)
#define PER(i, n) for(int i=(int)(n)-1; i>= 0; i--)
#define PERS(i, n)  for(int i=(int)(n); i>0; i--)
#define FOR(i, c) for(__typeof((c).begin()) i = (c).begin(); i!=(c).end(); i++)
#define RFOR(i, c)  for(__typeof((c).rbegin()) i=(c).rbegin(); i!=(c).end(); i++)
#define ALL(container)  (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) (container).size()
#define FILL0(n)  setfill('0') << right << setw(n)
#define mp(a, b)  make_pair(a, b)
#define toLower(c)  c+0x20
#define toUpper(c)  c-0x20
#define pb  push_back
#define eb  emplace_back

const int INF = 1e9;
const long long LLINF = 1e18;
const int MOD = 1000000007;
const double Pi = 3.14159265358979323146;

int main(){
  int n, m; cin >> n >> m;
  REP(i, m){
    int a;  cin >> a;
    n-=a;
  }
  cout << max(n, -1) << endl;
  return 0;
}


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

int main() {
  long long N,ans=0;
  cin>>N;
  string s;
  cin>>s;
  vector<tuple<int, int,int>> a(N);
  if(s.at(0)=='R'){
    get<0>(a.at(0))++;
  }
  else if(s.at(0)=='G'){
    get<1>(a.at(0))++;
  }
  else{
    get<2>(a.at(0))++;
  }
  
  for(int i=1;i<N;i++){
    get<0>(a.at(i))+=get<0>(a.at(i-1));
    get<1>(a.at(i))+=get<1>(a.at(i-1));
    get<2>(a.at(i))+=get<2>(a.at(i-1));
    if(s.at(i)=='R'){
      get<0>(a.at(i))++;
    }
    if(s.at(i)=='G'){
      get<1>(a.at(i))++;
    }
    if(s.at(i)=='B'){
      get<2>(a.at(i))++;
    }
  }
  //cout<<get<0>(a.at(3));
  for(int i=0;i<N-1;i++){
    for(int j=i+1;j<N;j++){
      char A,B;
      A=s.at(i);
      B=s.at(j);
      if((A=='R'&&B=='G')||(A=='G'&&B=='R')){
        ans+=get<2>(a.at(j))-get<2>(a.at(i));
        if((i+j)%2==0&&get<2>(a.at((i+j)/2))!=get<2>(a.at((i+j)/2-1))){
          ans--;
        }
      }
      else if((A=='R'&&B=='B')||(A=='B'&&B=='R')){
        ans+=get<1>(a.at(j))-get<1>(a.at(i));
        if((i+j)%2==0&&get<1>(a.at((i+j)/2))!=get<1>(a.at((i+j)/2-1))){
          ans--;
        }
      }
      else if((A=='G'&&B=='B')||(A=='B'&&B=='G')){
        ans+=get<0>(a.at(j))-get<0>(a.at(i));
        if((i+j)%2==0&&get<0>(a.at((i+j)/2))!=get<0>(a.at((i+j)/2-1))){
          ans--;
        }
      }
    }
  }
  cout<<ans;
         
      
}

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

signed main(){
  ios::sync_with_stdio( 0 );
  int n, c, k; cin >> n >> c >> k;
  vector< int > t( n );
  for( int i = 0; i < n; ++i ){
    cin >> t[ i ];
  }
  sort( t.begin(), t.end() );
  int ans = 0;
  {
    int ptr = 0;
    while( ptr < n ){
      ++ans;
      int ppl = 0;
      int z = ptr;
      while( ptr < n and ppl < c and t[ ptr ] - t[ z ] <= k ) ++ptr, ++ppl;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 764
n, m = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
a.sort(reverse=True)
r = 'Yes'
t = sum(a)
for i in range(m):
    if a[i] < t / (4 * m):
        r = 'No'
        break
print(r)

Measured memory_bytes: 2940
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public class Dice {

		int[] diceInit = new int[6];
		int[] dice = new int[6];

		/**
		 * サイコロを用意する
		 * @param nums
		 */
		public Dice(int[] nums) {
			dice = nums;
			diceInit = nums;
		}

		/**
		 * サイコロの状態を確認
		 */
		public int[] checkSurface() {
			return dice;
		}


		/**
		 * 入力された方向に移動
		 * @param order
		 */
		public void move(String order) {

			for(Character s : order.toCharArray()) {
				int buf;
				switch(s){
				case 'N':{
					buf = dice[0];
					dice[0] = dice[1];
					dice[1] = dice[5];
					dice[5] = dice[4];
					dice[4] = buf;
					break;
				}
				case 'E':{
					buf = dice[0];
					dice[0] = dice[3];
					dice[3] = dice[5];
					dice[5] = dice[2];
					dice[2] = buf;
					break;
				}
				case 'W':{
					buf = dice[0];
					dice[0] = dice[2];
					dice[2] = dice[5];
					dice[5] = dice[3];
					dice[3] = buf;
					break;
				}
				case 'S':{
					buf = dice[0];
					dice[0] = dice[4];
					dice[4] = dice[5];
					dice[5] = dice[1];
					dice[1] = buf;
					break;
				}
				case 'R': {
					buf = dice[1];
					dice[1] = dice[2];
					dice[2] = dice[4];
					dice[4] = dice[3];
					dice[3] = buf;
				}
				}
			}
		}

		/**
		 * 指定された状態になるまで回転を行う
		 * @param upper
		 * @param flont
		 * @return dice サイコロの状態
		 */
		public int[] checkRight(int upper, int front) {

			// サイコロを初期状態にリセット
			dice = diceInit;

			// 上面が指定の面になるまで回転
			for(int i=0; i<3; i++) {
				if(dice[0] == upper) break;
				move("W");
			}
			if(dice[0] != upper) {
				for(int i=0; i<3; i++) {
					if(dice[0] == upper) break;
					move("N");
				}
			}

			// 正面が指定の面になるまで回転
			for(int i=0; i<3; i++) {
				if(dice[1] == front) break;
				move("R");
			}

			return dice;
		}

	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		Boolean sameFlag = false;

		int[] nums1 = new int[6];
		int[] nums2 = new int[6];
		
		for(int i=0; i<6; i++) {
			nums1[i] = sc.nextInt();
		}

		for(int i=0; i<6; i++) {
			nums2[i] = sc.nextInt();
		}

		Dice dice1 = new Main().new Dice(nums1);
		Dice dice2 = new Main().new Dice(nums2);

		// 共通の数値２つを取り出す
		int upper = -1;
		int front = -1;
		for(int i=0; i<6; i++) {
			for(int j=0; j<6; j++) {
				if(nums1[i] == nums2[j]) upper = nums1[i];
			}
		}
		for(int i=0; i<6; i++) {
			if(nums1[i] == upper) continue;
			for(int j=0; j<6; j++) {
				if(nums1[i] == nums2[j]) front  = nums1[i];
			}
		}

		sc.close();

		int[] surface1 = dice1.checkRight(upper, front);
		int[] surface2 = dice2.checkRight(upper, front);

		if(Arrays.equals(surface1, surface2)) sameFlag = true;

		if(sameFlag) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}

	}

}



Measured memory_bytes: 26320
#include <cstdio>
#include <unordered_set>
std::unordered_set<int> S, W;
int A, B, C, D, E, F;

int main()
{
	scanf(" %d%d%d%d%d%d", &A, &B, &C, &D, &E, &F);
	S.reserve(F);
	for(int i = 0; C*i <= F; ++i)
	for(int j = 0; C*i + D*j <= F; ++j)
		S.insert(C*i + D*j);
	W.reserve(F);
	for(int i = 0; 100*A*i <= F; ++i)
	for(int j = 0; 100*(A*i + B*j) <= F; ++j)
		if(i || j) W.insert(100*(A*i + B*j));
	int res[2] = { 100*A, 0 }; // Mass: Sugar+Water, Sugar
	for(auto s: S)
	for(auto w: W)
	{
		if((s > E*w/100) || (s+w > F)) continue;
		if(s * res[0] > res[1] * (s+w))
			res[0] = s+w, res[1] = s;
	}
	printf("%d %d\n", res[0], res[1]);
	return 0;
}

Measured memory_bytes: 384
program main
implicit none
integer :: i, j, k, l, m, n
character(len=100) :: s(100), t
character(len=10000) :: res

read(*,*) n, l
do i = 1, n
   read(*,*) s(i)(1:l)
end do
do j = 1, n
do i = 2, n
   if( lle( s(i-1)(1:l), s(i)(1:l) ) .eqv. .false. ) then
      t(1:l)      = s(i)(1:l)
      s(i)(1:l)   = s(i-1)(1:l)
      s(i-1)(1:l) = t(1:l)
   end if
end do
end do
do i = 1, n
   do j = 1, l
      k = (i-1)*l +j
      res(k:k) = s(i)(j:j)
   end do
end do
write(*,*) res(1:n*l)


end program main



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

int main() {
  int N,D,X;
  cin >> N >> D >> X;
  int A=0;
  int sum=0;
  for(int i=0;i<N;i++){
    cin >> A;
    sum += (D-1)/A;
  }
  cout << sum + X + N << endl;

}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
multimap<string, int> m;
int main()
{
	int n;
	scanf("%d",&n);
	while(n--)
	{
		int t;
		scanf("%d",&t);
		if(t == 0)
		{
			string x;
			int y;
			cin >> x >> y;
			m.insert(make_pair(x, y));
		}
		else if(t == 1)
		{
			string x;
			cin >> x;
			if(m.count(x))
			{
				map<string, int>::iterator it, it2;
				it = m.lower_bound(x);
				it2 = m.upper_bound(x);
				for(; it!=it2; it++)
				{
					cout << (*it).second << endl;
				}
			}
		}
		else if(t == 2) 
		{
			string x;
			cin >> x;
			m.erase(x);
		}
		else if(t == 3)
		{
			string l, r;
			cin >> l >> r;
			map<string, int>::iterator it, it2;
			it = m.lower_bound(l);
			it2 = m.upper_bound(r);
			for(; it!=it2; it++)
			{
				cout << (*it).first << " " << (*it).second << endl;
			}
		}
	}
}


Measured memory_bytes: 24952
#include<bits/stdc++.h>
#define speed_up ios_base::sync_with_stdio(false); cin.tie(NULL)
#define ll long long
#define ara(A,N) sort(A,A+N)
#define rev(A,N) sort(A,A+N,greater<int>())
using namespace std;
int main()
{
  speed_up;
  int i, j, k, a = 0, b = 0;
  int sx, sy, tx, ty;
  cin>>sx>>sy>>tx>>ty;

  for(i = sy; i<ty; i++)
  {
      cout<<"U";
      a++;
  }
  for(i = sx; i<tx; i++)
  {
      cout<<"R";
      b++;
  }
  while(a--)
  {
      cout<<"D";
  }
  while(b--)
  {
      cout<<"L";
  }
  cout<<"L";
  for(i = sy; i<=ty; i++)
  {
      cout<<"U";
      a++;
  }
  for(i = sx; i<=tx; i++)
  {
      cout<<"R";
      b++;
  }
  cout<<"D";
  cout<<"R";
  a++;
  b++;
  while(a--)
  {
      cout<<"D";
  }
  while(b--)
  {
      cout<<"L";
  }
  cout<<"U";







      return 0;
}


Measured memory_bytes: 3632
/*
 ID: swagchicken1
 PROG:
 LANG: C++11
 */

#include <iostream>
#include <tuple>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iomanip>
#include <ctime>
#include <cctype>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;

#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)

//#define endl '\n';

#define mp make_pair
#define pb push_back
#define f first
#define s second

const int MOD = 1000000007;
double PI = 4*atan(1);


int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    //     ofstream fout("trapped.out");
    //      ifstream fin("trapped.in");
    int H,W,h,w; cin >> H >> W >> h >> w;
    cout << (H-h)*(W-w);
    
    //  fin.close();
    //    fout.close();
}


Measured memory_bytes: 256
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())

uf = UnionFind(N)

for i in range(M):
    A, B = map(int, input().split())
    uf.union(A-1, B-1)

ml = 0
for n in uf.roots():
    ml = max(ml, uf.size(n))

print(ml)

Measured memory_bytes: 18416
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);(i)--)
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);(i)--)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }

template<typename T> class BIT {
    int n;
    vector<T> dat;
public:
    void init(int in) {
        n = in + 1;
        dat.clear();
        dat.resize(n + 1, 0);
    }
    T sum(int i) {
        T ret = 0;
        while (i >= 0) {
            ret += dat[i];
            i = (i & (i + 1)) - 1;
        }
        return ret;
    }
    void add(int i, T x) {
        while (i <= n) {
            dat[i] += x;
            i |= i + 1;
        }
    }
};

int main() {
    int n;
    cin >> n;
    VI a(n), sorted(n);
    FOR(i, 0, n) {
        cin >> a[i];
        sorted[i] = a[i];
    }
    SORT(sorted);
    int ok = 0, ng = n;
    BIT<ll> bit;

    ll border = (((ll)n * (n + 1) / 2) + 1) / 2;
    while (ng - ok > 1) {
        int mid = (ng + ok) / 2;
        int midnum = sorted[mid];
        bit.init(2 * n + 1);
        int sum = 0;
        bit.add(sum + n, 1);
        ll result = 0;
        FOR(i, 0, n) {
            sum += (a[i] >= midnum ? 1 : -1);
            result += bit.sum(sum + n);
            bit.add(sum + n, 1);
        }
        if (result >= border)ok = mid;
        else ng = mid;
    }
    cout << sorted[ok] << endl;
}


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

#define endl '\n'
#define lfs cout<<fixed<<setprecision(10)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (m) - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
void chmin(T &a,T b){if(a>b)a=b;}
template<typename T>
void chmax(T &a,T b){if(a<b)a=b;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,0,-1,0,1,1,-1,-1};
vector<ll>dy={0,1,0,-1,1,-1,1,-1};
template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}
ostream &operator<<(ostream &os, pair<ll, ll>&p){
  return os << p.first << " " << p.second;
}  
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  ll h,n;cin>>h>>n;
  vector<ll>a(n),b(n);
  rep(i,0,n)cin>>a[i]>>b[i];
  vector<ll>dp(h+1,INF);
  dp[0]=0;
  rep(i,0,h){
    rep(j,0,n){
      chmin(dp[min(h,i+a[j])],dp[i]+b[j]);
      //cout<<min(h,i+a[i]) spa dp[i]+b[i]<<endl;
    }
  }
  //debug(dp,h);
  cout<<dp[h]<<endl;
  return 0;
}

Measured memory_bytes: 384
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

bool dpX[8000][20000];
bool dpY[8000][20000];

vector<pair<char, int>> RLE(string &s){
	int cnt = 0;
	vector<pair<char, int>> res;
	rep(i,s.size()){
		++cnt;
		if(i == s.size()-1){
			res.push_back(make_pair(s[i], cnt));
			break;
		}
		if(s[i] != s[i+1]){
			res.push_back(make_pair(s[i], cnt));
			cnt = 0;
		}
	}
	return res;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s1;
	cin >> s1;
	int x, y;
	cin >> x >> y;
	x += 8000;
	y += 8000;
	string s;
	int ini_x = 8000, ini_y = 8000;
	bool flag = true;
	rep(i,s1.size()){
		if(flag){
			if(s1[i] == 'F') ++ini_x;
			else{
				s += s1[i];
				flag = false;
			}
		}
		else s += s1[i];
	}
	vector<int> fx, fy;
	vector<pair<char, int>> vp = RLE(s);
	bool turn = true;
	rep(i,vp.size()){
		if(vp[i].first == 'T'){
			if(vp[i].second & 1) turn = !turn;
		}
		else{
			if(turn) fx.push_back(vp[i].second);
			else fy.push_back(vp[i].second);
		}
	}
	dpX[0][ini_x] = true;
	dpY[0][ini_y] = true;
	rep(i,fx.size()){
		rep(j,20000){
			if(dpX[i][j]){
				if(j+fx[i] < 20000) dpX[i+1][j+fx[i]] = true;
				if(j-fx[i] >= 0) dpX[i+1][j-fx[i]] = true;
			}
		}
	}
	rep(i,fy.size()){
		rep(j,20000){
			if(dpY[i][j]){
				if(j+fy[i] < 20000) dpY[i+1][j+fy[i]] = true;
				if(j-fy[i] >= 0) dpY[i+1][j-fy[i]] = true;
			}
		}
	}
	if(dpX[fx.size()][x] && dpY[fy.size()][y]) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 80768
let id x = x
let id' x = 1
let n = Scanf.scanf "%d\n" id

let g = (fun () -> Scanf.scanf "%d\n" id)
  
let repeat f =
  let rec loop acc = function
    | 0 -> List.rev acc
    | n -> loop (f () :: acc) (n - 1) in
  loop []
 
let r = repeat (fun () -> Scanf.scanf "%d " id) n
  
let rec check = function
  | [a] -> true
  | a :: rest ->
     match rest with
     | [b] -> if (a mod 2) = (b mod 2) then true else false
     | b :: rest2 ->
	match rest2 with
	| c :: rest3 -> if (a mod 2) = (b mod 2) then check ((a+b) :: rest2) else
	    if (a mod 2) = (c mod 2) then check ((a+c) :: b :: rest3) else check ((b+c) :: a :: rest3)

let ansbool = check r

let ans = if ansbool = true then "YES" else "NO"
    
let () = Printf.printf "%s\n" ans


Measured memory_bytes: 7296
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+b,(a).begin()+c // コンテナ a の 要素 b から c へのイテレータ
#define MOD 1000000007
#define INF 1000000000
typedef pair<int64_t, int64_t> PII;
typedef vector<int64_t> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

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

int64_t N; cin >> N;
VI d(N); rep(i, 0, N) cin >> d[i];
sort(ALL(d));

cout << d[N/2] - d[N/2 - 1] << endl;



}

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



Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
using P = pair<int,int>;
const int MOD = 1000000007;

int main() {
    ll ans=0,mini=1LL<<60,temp,n;
    cin>>n;
    rep(i,5) {
        cin>>temp;
        mini=min(mini,temp);
    }
    ans=(n+mini-1)/mini+4;
    cout<<ans<<endl;
}


Measured memory_bytes: 256
from collections import deque
H,W = map(int, input().split())
maze = [input() for _ in range(H)]
cnt_wall = 0
for y in range(H):
    for x in range(W):
        if maze[y][x]=="#":
            cnt_wall += 1
            
q = deque([(0,0)])
dist = [[float('inf')]*W for _ in range(H)]
dist[0][0] = 1

while q:
    y,x = q.popleft()
    #print(y,x,step)
    if (y,x)==(H-1,W-1):
        print(H*W - cnt_wall - dist[y][x])
        break
    for dy,dx in zip([0,0,1,-1], [1,-1,0,0]):
        nx,ny = x+dx, y+dy
        if not(0<=ny<H and 0<=nx<W):
            continue
        if maze[ny][nx]=="." and dist[ny][nx]==float('inf'):
            q.append((ny, nx))
            dist[ny][nx] = dist[y][x] + 1
else:
    print(-1)

Measured memory_bytes: 3316
#include<bits/stdc++.h>
#define int long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define PI acos(-1)
#define bp __builtin_popcountll
#define all(x) x.begin(),x.end()
#define sp fixed<<setprecision
#define pii pair<long long,long long>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

int MOD = (1e9)+7;
const int N = (1e6)+5;

signed main()
{
    FAST
    int tc=1;
    //cin>>tc;
    for(int ti=1;ti<=tc;ti++)
    {
        int n;
        cin>>n;
        int ans= 0;
        for(int a=1;a<=n;a++)
        {
            for(int b=1;b<=n;b++)
            {
                int g = __gcd(a,b);
                for(int c=1;c<=n;c++)
                {
                    ans+=__gcd(g,c);
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
/*
Test Case
*/


Measured memory_bytes: 3652
#include<stdio.h>
int main()
{
    int X,Y,Z,tmp=0;
    char s[101];
    // 整数の入力
    scanf("%d %d %d", &X, &Y, &Z);
    tmp=X;
  	X=Y;
  	Y=tmp;
    
 
  	tmp=X;
  	X=Z;
  	Z=tmp;
    
    // 出力
    printf("%d %d %d",X,Y,Z);
    return 0;
}

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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

// Vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
	int len = v.size();
  s << "[";
	for (int i = 0; i < len; i++) {
    if (i > 0) s << ", ";
		s << v[i];
	}
  s << "]";
	return s;
}

// Supports two operations.
// - Updates a single element.
// - Returns a sum of a range.
// Verified: CF573Div1D
class BinaryIndexedTree {
 private:
  int n;
  vector<int> xs;
 public:
  BinaryIndexedTree(int n) : n(n), xs(n) {}

  // Adds x to the i-th element.
  void Add(int i, int x) {
    int cur = i;
    while (cur < n) {
      xs[cur] += x;
      cur = cur | (cur + 1);
    }
  }

  // Returns a sum of a range [l r).
  int SumOfRange(int l, int r) {
    if (l >= r) return 0;
    if (l > 0) {
      return SumOfRange(0, r) - SumOfRange(0, l);
    }
    int s = 0;
    int i = r - 1;
    while (i >= 0) {
      s += xs[i];
      i = (i & (i + 1)) - 1;
    }
    return s;
  }
};

int64 Solve() {
  string s;
  cin >> s;

  int n = s.length();
  vector<int> xs(n);
  for (int i = 0; i < n; i++) {
    xs[i] = s[i] - 'a';
  }
  
  vector<int> cs(26);
  for (int x : xs) {
    cs[x]++;
  }
  
  int odd_count = 0;
  for (int c : cs) {
    if (c % 2 == 1) odd_count++;
  }
  if (odd_count >= 2) return -1;

  vector<int> ps(n, -1);
  vector<vector<int>> x_to_ps(26);
  int l_count = 0;
  for (int i = 0; i < n; i++) {
    int x = xs[i];
    if (x_to_ps[x].size() * 2 + 1 < cs[x]) {
      ps[i] = l_count;
      x_to_ps[x].push_back(ps[i]);
      l_count++;
    } else if (x_to_ps[x].size() * 2 + 1 == cs[x]) {
      ps[i] = n / 2;
      x_to_ps[x].push_back(ps[i]);
    } else {
      ps[i] = n - 1 - x_to_ps[x][cs[x] - 1 - x_to_ps[x].size()];
      x_to_ps[x].push_back(ps[i]);
    }
  }
  if (DEBUG) cout << "ps: " << ps << endl;

  BinaryIndexedTree bit(n);
  int64 sum = 0;
  for (int i = 0; i < n; i++) {
    bit.Add(ps[i], 1);
    sum += bit.SumOfRange(ps[i] + 1, n);
  }
  return sum;
}

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

  cout << Solve() << endl;
}

Measured memory_bytes: 3980
#include <bits/stdc++.h>
using namespace std;
 
typedef long long               ll;
typedef long double             ld;
 
 
#define racecar          ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define si(a)            scanf("%d", &a)
#define si2(a,b)         scanf("%d %d", &a,&b)
#define sll(a)           scanf("%I64d",&a)
#define sll2(a,b)        scanf("%I64d %I64d",&a,&b)
#define pb               push_back
#define pi(a)            printf("%d",int(a))
#define pll(a)           printf("%I64d",ll(a))
#define all(x)           (x).begin(),(x).end()
#define rall(x)          (x).rbegin(),(x).rend()
#define ps               printf(" ")
#define nln              printf("\n")
#define ff               first
#define ss               second
#define vi               vector<int>
#define vll              vector<ll>
#define vstr             vector<string>
#define vc               vector<char>
#define pii              pair<int,int>
#define PLL              pair<ll,ll>
#define PI               acos(-1)
#define sq(x)            x*x
#define forr(i,a,b)      for(ll i=ll(a);i<ll(b);i++)
#define forn(i,a,b)      for(ll i=ll(a);i>ll(b);i--)
#define max3(a,b,c)      max(a,max(b,c))
#define max4(a,b,c,d)    max(max3(a,b,c),d)
#define min3(a,b,c)      min(a,min(b,c))
#define mod              1000000007
#define inf              9223372036854775807
 
ll power(ll b,ll n)
{
    if(n==0) return 1;
    else if(n%2) return b*power(b,n/2)*power(b,n/2);
    else return power(b,n/2)*power(b,n/2);
} 
 
ld root(ll n,ll r)
{
    ld dif=0.0001;
    ld guess=n/2.0;
    while(abs(pow(guess,r)-n)>=dif)
    {
        ld temp=pow(guess,r)-n;
        ld tmp=r*pow(guess,r-1);
        guess-=temp/tmp;
    }
    return guess;
}
 
void fileio()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
}
 
 
int solve()
{
	ll n,a,b;
	sll(n);
	sll2(a,b);
	ll e=n*a;
	ll tot=min(e,b);
	pll(tot);
	
	return 0;
}
 
int main()
{   
 
//    racecar;
//    cout<<fixed<<setprecision(6);
//    fileio();
    solve();
}
 
 
 
///    Before submission=>
///    ***check for integer overflow,array bounds
///    ***check for n

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


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


	string s;
	cin >> s;
	bool valid = true;

	int n = s.length(), i, j, k, ct = 0, c = 0;
	if (s[0] != 'A') valid = false;
	for (i = 2; i < n - 1; i++) {
		if (s[i] == 'C') ct++;
	}
	if (ct != 1) valid = false;
	for (i = 0; i < n; i++) {
		if ((s[i] >= 'A') && (s[i] <= 'Z')) c++;
	}
	if (c != 2) valid = false;

	if (valid) cout << "AC\n";
	else cout << "WA\n";

	return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

n = int(input())
a_l = list(map(int, input().split()))
b_l = list(map(int, input().split()))
c_l = list(map(int, input().split()))

ans = 0
for i in range(n):
    ans += b_l[a_l[i]-1]
    if i != 0 and a_l[i] == a_l[i-1]+1:
        ans += c_l[a_l[i]-2]
print(ans)

Measured memory_bytes: 3064
N, Y = map(int, input().split())
Y /= 1000
total = 0
flag = 0

for A in range(N+1):
    for B in range(N+1):
        C = N - A - B
        if C<0:
            break
        total = 10 * A + 5 * B + C
        if total == Y:
            print(A, B, C)
            flag = 1
            break
    if flag == 1:
        break

if flag == 0:
    print('-1 -1 -1')

Measured memory_bytes: 9192
n=int(input())
s=input()
l=[]
for i in s:
    l.append(i)
#print(l)
count=0
for i in range(len(l)-2):
    if l[i]=="A" and l[i+1]=="B" and l[i+2]=="C":
            count+=1
print(count)

Measured memory_bytes: 3064
#include<iostream>
#define yes "YES"
#define no "NO"
using namespace std;

// Problem https://atcoder.jp/contests/abc060/tasks/abc060_b
// 3rd C++ TRY

bool solver(int MULTIBASE,int DEVIDENUM,int MODNUM){
    bool result;
    result = false;
    for(int j=1;j<=DEVIDENUM;j++){
        int asmulti;
        asmulti = j * MULTIBASE;
        int asmultiMod;
        asmultiMod = asmulti % DEVIDENUM;
        if(asmultiMod == MODNUM){
            result = true;
            break;
        }
    }
    return result;
}

int main(void){
    bool answer;
    answer = false;
    int A,B,C;
    cin >> A >> B >> C;
    answer = solver(A,B,C);
    if(answer){
        cout << yes << endl;
    }
    else{
        cout << no << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T = int> void print(vector<T> v){for(auto a:v)cout<<a<<" ";cout<<endl;}

/*
*/

ll n,x,y;
ll dp[2010][2010];
ll ans[2010]={};

int main(void){
	cin>>n>>x>>y;
	reg(i,1,n)reg(j,1,n)dp[i][j]=1e9;
	reg(i,1,n){
		queue<ll> Q;
		dp[i][i]=0;
		Q.push(i);
		while(!Q.empty()){
			ll p = Q.front();Q.pop();
			if(p<n && dp[i][p+1] > dp[i][p]+1){
				dp[i][p+1] = dp[i][p]+1;
				Q.push(p+1);
			}
			if(p>0 && dp[i][p-1] > dp[i][p]+1){
				dp[i][p-1] = dp[i][p]+1;
				Q.push(p-1);
			}
			if(p==x && dp[i][y] > dp[i][p]+1){
				dp[i][y] = dp[i][p]+1;
				Q.push(y);
			}
			if(p==y && dp[i][x] > dp[i][p]+1){
				dp[i][x] = dp[i][p]+1;
				Q.push(x);
			}
		}
	}
	reg(i,1,n)reg(j,1,n)ans[dp[i][j]]++;
	reg(i,1,n-1)cout<<ans[i]/2<<endl;
	return 0;
}

Measured memory_bytes: 31744
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void) {
	int a, b;
	scanf("%d%d", &a, &b);
	if (a <= 8 && b <= 8) {
		printf("Yay!\n");
	}
	else {
		printf(":(\n");
	}
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <map>

int main() {
    using namespace std;
    long long n, cnt=0;
    cin >> n;
    std::string si;
    map<std::string, long long> m;
    for (long long i=0; i<n; i++){
        cin >> si;
        sort(si.begin(), si.end());
        if (m.count(si)) cnt+=m[si];
        m[si]++;
    }
    cout << cnt;
}

Measured memory_bytes: 11396
#include <bits/stdc++.h>
      
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
#define SHOWA(x,n) for( int yui = 0; yui < n; yui++ ){ cout << x[yui] << " "; } cout << endl

#define pb emplace_back
#define fi first
#define se second

using namespace std;

typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
     
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-12;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }

ll in(){ long long int x; scanf( "%lld" , &x ); return x; }
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }

// head

int n;
ll a[200010];
ll sum;

vpl v;

int main(){

  n = in();
  REP( i , n ){
    a[i] = in();
    v.pb( a[i] , i );
  }
  SORT( v );

  set<int> ss;
  ss.insert( -1 );
  ss.insert( n );
  YYS( w , v ){
    ll x = w.fi;
    ll id = w.se;
    auto ne = ss.lower_bound( id );
    auto pr = ne;
    pr--;
    ll l = id - (*pr);
    ll r = (*ne) - id;
    sum += x * ( l * r );
    ss.insert( id );
  }

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


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

typedef long long ll;

int main()
{
    ll i,j;
    vector<ll> lucas(87);
    lucas.at(0) = 2LL;
    lucas.at(1) = 1LL;
    for(i = 2;i < 87;++i){
        lucas.at(i) = lucas.at(i-1) + lucas.at(i-2);
    }
    int n;
    cin >> n;
    cout << lucas.at(n) << endl;
    return 0;
}

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

int main() {
	int a[101] = {},i = 1,max = 0,tmp;

	while (cin >> tmp) {
		a[tmp]++;
		i++;
	}

	for (int j = 1; j < 100; j++) {
		if (a[j] > max) {
			max = a[j];
		}
	}

	for (int j = 1; j < 100; j++) {
		if (a[j] == max) {
			cout << j << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1160
a ,b ,c = map(int,input().split())
#4*a*b < (c-a-b)**2　両辺を２乗することを思いつかなかった。
if 4*a*b < (c-a-b)**2 and (c-a-b) > 0:
    print("Yes")
else:
    print("No")


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

int main(){
        int n;
        string s;
        vector<string> v;

        cin >> n;
        for (int i = 0; i < n; ++i){
                cin >> s;
                v.push_back(s);
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        size_t ans  = v.size();
        cout << ans << endl;
}

Measured memory_bytes: 11664
a,b,c = map(int,input().split())
d = int(input())
count = 0
while True:
    if a < b:
        if b < c:
            break
        else:
            c *= 2
            count += 1
    else:
        b *= 2
        count += 1
print("Yes" if count <= d else "No")

Measured memory_bytes: 9208
#include <bits/stdc++.h>
#define io() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); srand(time(NULL));
 
using namespace std;

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

signed main(){
    io();
    int n, l; cin >> n >> l;
    vector<string> v(n);
    for(int i = 0; i < n; ++i){
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    string ans = "";
    for(int i = 0; i < n; ++i){
        ans += v[i];
    }
    return cout << ans << '\n', 0;
}

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

#ifdef LOCAL
#define debug(var) cerr << #var << " = " << var;
#else
#define debug(var)
#endif

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

void solve() {
	int n; cin >> n;
	string s; cin >> s;
	int x = 0, ans = 0;
	for (int i = 0; i < n; ++i) {
		if (s[i] == 'I') ++x;
		else if (s[i] == 'D') --x;
		ans = max(ans, x);
	}
	cout << ans;
}

int main() {
	init();
	int t = 1; //scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}


Measured memory_bytes: 256
q=Array.new n=gets.to_i,M=-1
s=*q
g=$<.map{|l|i,*c=l.split.map &:to_i
!i&&next
c.reject!{|v|v<0}
c.map{|j|q[j]=i}
c[1]&&(a,b=c
s[a],s[b]=b,a)
[i,c]}.compact.sort
d=->f,i,x{g[i][2]=x
g[i][3]=(g[i][1].map{|j|f[f,j,x+1]}.max||M)+1}
d[d,q.index(M),0]
g.map{|v|i,c,d,h=v
[i,p=q[i],s[i],c.size,d,h,p<0?:root:c[0]?"internal node": :leaf]}.map{|v|puts ["node %d: parent",:sibling,:degree,:depth,:height,"%s"]*" = %d, "%v}

Measured memory_bytes: 6136
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        int H,W,i,j;
        while(true){	
            H = input.nextInt();	
            W = input.nextInt();	
        if(H + W <= 0)break;	
           for (i = 0; i < H; i++ ){
            for (j = 0; j < W; j++ ){
                if((i == 0 || i == H-1) || (j == 0 || j == W-1))
                    System.out.print("#");
                else 
                    System.out.print(".");
            }
             System.out.println("");
		    }
		    System.out.println();
        }
    }
}


Measured memory_bytes: 32936
#include <bits/stdc++.h> 
using namespace std; 
typedef long long int ll;
typedef long double ld;
typedef unsigned long long int ull;
const long long int m=pow(10,9)+7;

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,y;
    cin>>n>>y;
    for(ll i=0;i<=n;i++) 
    {
        for(ll j=0;j<=n-i;j++)
        {
            if(i*10000+j*5000+(n-i-j)*1000==y) 
            {
                cout<<i <<" "<<j<<" "<<n - i - j<<endl;
                return 0;
            }
        }
    }
    cout<<"-1 -1 -1"<<endl;
    return 0;
}

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

int main() {
  
  string str="0121313113131";
  int x=0, y=0;
  
  cin >> x >> y;
  
  if(str.at(x)==str.at(y)) {
    
    cout << "Yes" << endl;
    
  } else {
    
    cout << "No" << endl;
    
  }
  
  return 0;
  
}

Measured memory_bytes: 256
#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 all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(_v) for(auto _x:_v){cout<<_x<<" ";}cout<<endl
#define printVS(vs) for(auto x : vs){cout << x << endl;}
#define printVV(_vv) for(auto _v:_vv){for(auto _x:_v){cout<<_x<<" ";}cout<<endl;}
#define printP(p) cout << p.first << " " << p.second << endl
#define printVP(vp) for(auto p : vp) printP(p);

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

// #define double long double

typedef complex<double> P;
typedef vector<P> G;
#define here(g, i) g[i]
#define next(g, i) g[(i + 1) % g.size()]
#define prev(g, i) g[(i - 1 + g.size()) % g.size()]
const double EPS = 1e-6;
const double INF = 1e12;
const double PI = acos(-1);

P readP() {
    double x, y;
    cin >> x >> y;
    return P(x, y);
}

// rot p around q by theta (counter-clockwise)
P rotP(P p, P q, double theta) {
    p -= q;
    double x = p.real(), y = p.imag();
    p = P(x * cos(theta) - y * sin(theta), x * sin(theta) + y * cos(theta));
    p += q;
    return p;
}

P center(P p, P q) {
    // P v = q - p;
    // double theta = asin(abs(v) / 2);
    // v *= (1 / abs(v));
    // P u = rotP(v, p, theta);
    // return p + u;

    // P v = q - p;
    // P h = v * P(0., 1.) / abs(v);
    // return p + (v / 2.) + h;

    P v = q - p;
    P h = P(v.imag(), -v.real());
    h /= abs(h);
    h *= sqrt(1 - norm(v / 2.));
    P c = p + (v / 2.) + h;
    return c;
}

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

    int n;
    while (cin >> n, n) {
        vector<P> p(n);
        rep(i, n) p[i] = readP();

        int ans = 1;
        rep(i, n) {
            rep2(j, i + 1, n) {
                if (i == j) continue;
                if (norm(p[i] - p[j]) > 4. + EPS) continue;
                rep(s, 2) {
                    P c = (s ? center(p[i], p[j]) : center(p[j], p[i]));
                    int cnt = 2;
                    rep(k, n) {
                        if (k == i || k == j) continue;
                        if (norm(p[k] - c) < 1. + EPS) {
                            cnt++;
                        }
                    }
                    ans = max(ans, cnt);
                }
            }
        }

        cout << ans << endl;
    }
}

Measured memory_bytes: 3260