akhauriyash/Code-Regression huggingface dataset:
/*Read the problem carefully before starting to work on it*/
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;

#define pb push_back
#define eb emplace_back
#define mp(x,y) make_pair(x,y)
#define mod 1000000007

double PI=3.1415926535897932384626;

//template<typename T> T power(T x,T y,ll m=mod){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}

//typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ost;

//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rnd(x, y) uniform_int_distribution<ll>(x, y)(rng)

//struct custom_hash {
//    static uint64_t splitmix64(uint64_t x) {
//        // http://xorshift.di.unimi.it/splitmix64.c
//        x += 0x9e3779b97f4a7c15;
//        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
//        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
//        return x ^ (x >> 31);
//    }
//    size_t operator()(uint64_t x) const {
//        static const uint64_t FIXED_RANDOM = 
//            chrono::steady_clock::now().time_since_epoch().count();
//        return splitmix64(x + FIXED_RANDOM);
//    }
//};

#define fi first
#define se second

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll k;
	cin>>k;
	ll sum=0;
	for(ll i=1;i<=k;i++)
	{
		for(ll j=1;j<=k;j++)
		{
			for(ll j1=1;j1<=k;j1++)
			{
				sum+=(__gcd(i,__gcd(j,j1)));
			}
		}
	}
	cout<<sum;
    return 0;
}


//252908XL

/*
comments:-

*/


Measured memory_bytes: 3624
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize("Ofast")
//*********************************************DO IT NOW****************************************************************
#include<bits/stdc++.h> 
#include<random>
//#define int long long   
#define pp pair<int,int> 
#define ss second 
#define ff first 
#define pb push_back
#define mod 1000000007
#define pi 3.14159265359
#define mk(arr,n,type)  type *arr=new type[n];
#define sl s1.length();
#define yes cout<< "YES"<<endl
#define no  cout<< "NO"<<endl
#define all(v) (v).begin(),(v).end()
#define s(v)   sort(v,v+n)
#define  mt mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define read(a,n) for(int i=0;i<n;i++)cin>>a[i]
#define print(a,n) for(int i=0;i<n;i++)cout<<a[i]<<" "
using namespace std;
//**********************************************DO IT NOW***************************************************************
void fastio()
{  
  #ifndef ONLINE_JUDGE
  freopen("INPUT.txt","r",stdin);
  freopen("OUTPUT.txt","w",stdout); 
  #endif
  ios_base :: sync_with_stdio(false); 
  cin.tie(NULL) ; 
  cout.tie(NULL);
}
int dp[101][1001],ans1=1e9,dp1[1000001];
int num[10];
int a[1000000];
int main()
{   
    fastio();
    int t=1;
   // cin>>t;
    while(t--)
    {
        string s,ss;
        cin>>s;
        ss=s;
        reverse(s.begin(),s.end());
        if(ss==s)
        cout<<"Yes";
        else
        cout<<"No";
    }
    
}
// 🍪 🍪 🍪


Measured memory_bytes: 3604
#include <bits/stdc++.h>
const int N=305;
char s[N];
int k,n;
int a[N];
 
int judge1(){
	for(int i=n;i<n+n;++i)
		if(a[i]!=a[i+n])return false;
	return true;
}
int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);std::cout.tie(0);
	std::cin>>s>>k;
	n=strlen(s);
	if(n==1){
		std::cout<<k/2<<'\n';
		return 0;
	}
	for(int i=n;i<n+n+n;++i)
		s[i]=s[i-n];
	for(int i=1;i<n+n+n;++i)
		if(s[i]==s[i-1]){
			a[i]=1;
			s[i]=0;
		}
//	for(int i=0;i<n+n;++i)
//		std::cout<<a[i];
	long long ans1=0,ans2=0,ans3=0;
	for(int i=0;i<n;++i)
		ans1+=a[i];
	for(int i=n;i<n+n;++i)
		ans2+=a[i];
	for(int i=n+n;i<n+n+n;++i)
		ans3+=a[i];
	//std::cout<<ans1<<' '<<ans2<<' '<<ans3<<'\n';
 	if(!judge1())
		std::cout<<(ans1+ans2)*(k/2)+ans1*(k&1)<<'\n';
	else std::cout<<ans1+ans2*(k-1)<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi           first
#define se           second
#define ll           long long
#define pb           push_back
#define mp           make_pair
#define pll          pair<ll,ll>
#define pii          pair<int,int>
#define all(x)       (x).begin(),(x).end()
#define isWorking()  cout<<"Wroking"<<endl
#define FOR(i,x,y)   for(int i=x; i<y; i++)
#define SORT(x)      sort(x.begin(),x.end())
#define PRINT(ok)    cout<<(ok? "YES":"NO")<<endl
#define Fast_Input   ios_base :: sync_with_stdio(false), cin.tie(NULL);
typedef vector < int > VI;
const ll mod= 1e9+7,INF=1e18,mx= 5e6+5,mn=100;
int testCase=1,cas=0;

int main() {
    Fast_Input

    //cin>>testCase;
    while(testCase--){
        int n; cin>>n;
        string str; cin>>str;
        stack <char> st;
        deque <char> Ans;

        for(int i=0; i<n; i++){
            if(str[i]=='('){
                st.push('(');
                Ans.push_back('(');
                continue;
            }

            if(st.empty()){
                Ans.push_front('(');
                Ans.push_back(')');
                continue;
            }

            st.pop();
            Ans.push_back(')');
        }
        while(st.size()){
            Ans.push_back(')');
            st.pop();
        }

        while(Ans.size()){
            cout<<Ans.front();
            Ans.pop_front();
        }
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long h,w,ans=0;
  cin >> h >> w;
  char c[h][w];
  long long dist[h][w];
  bool used[h][w];
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      dist[i][j]=1e9;
      used[i][j]=false;
    }
  }
  queue<pair<int,int> > que;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin >> c[i][j];
      if(c[i][j]=='#'){
        dist[i][j]=0;
        que.push(make_pair(i,j));
        used[i][j]=true;
      }
    }
  }
  while(!que.empty()){
    int ii=que.front().first,jj=que.front().second;
    que.pop();
    if(ii>0){
      dist[ii-1][jj]=min(dist[ii-1][jj], dist[ii][jj]+1ll);
      if(!used[ii-1][jj]){
        que.push(make_pair(ii-1,jj));
        used[ii-1][jj]=true;
      }
    }
    if(ii<h-1){
      dist[ii+1][jj]=min(dist[ii+1][jj], dist[ii][jj]+1ll);
      if(!used[ii+1][jj]){
        que.push(make_pair(ii+1,jj));
        used[ii+1][jj]=true;
      }
    }
    if(jj>0){
      dist[ii][jj-1]=min(dist[ii][jj-1], dist[ii][jj]+1ll);
      if(!used[ii][jj-1]){
        que.push(make_pair(ii,jj-1));
        used[ii][jj-1]=true;
      }
    }
    if(jj<w-1){
      dist[ii][jj+1]=min(dist[ii][jj+1], dist[ii][jj]+1ll);
      if(!used[ii][jj+1]){
        que.push(make_pair(ii,jj+1));
        used[ii][jj+1]=true;
      }
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      ans=max(ans, dist[i][j]);
    }
  }
  cout << ans << endl;
  return 0;
}



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

#define rep(i,n) for(int i=0; i<n; i++)
#define rept(i,a,b) for(int i=a; i<b; i++)
#define ll long long

int main() {
	ll a, b;
	cin >> a >> b;

	int x = abs(a - b);
	if(x % 2 == 0){
		cout << (a + b) / 2 << endl;
	}else{
		cout << "IMPOSSIBLE" << endl;
	}




    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define endl "\n"
#define pii pair<int,int> 
#define ff first
#define ss second
#define mii map<int,int>
#define si set<int>
#define sti stack<int>
#define qi queue<int>
#define vi vector<int>
#define pq priority_queue<int>
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int M=1e9+7;

void solve(){
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++) cin>>a[i];
	if(n==1){
		cout<<0<<endl;
	}
	sort(a,a+n);
	int ans=0;
	ans+=a[n-1];
	for(int i=n/2;i<n-1;i++) ans+=2*a[i];
	if(n%2==1) ans-=a[n/2];
	cout<<ans<<endl;
}

int32_t main(){
	IOS;
	int t=1;
	//cin>>t;
	while(t--){
		solve();	
	}
}

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

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            var l1 = Console.ReadLine();
            var l2 = Console.ReadLine();
            var num = int.Parse(l1);
            var aa = new List<int>();
            var bs = l2.Split(' ').Select(n => int.Parse(n)).ToArray();
            foreach (int x in bs)
            {
                var xx = x - 1; // 0 based new b
                if (xx < 0 || xx > aa.Count)
                {
                    Console.WriteLine(-1);
                    return;
                }
                aa.Insert(xx, xx);
            }
            foreach (var x in aa)
            {
                Console.WriteLine(x + 1);
            }
        }
    }
}


Measured memory_bytes: 13396
local mfl = math.floor
local mce = math.ceil
local function comp(a, b)
  return a[1] < b
end

local function lower_bound(ary, x)
  local num = #ary
  if num == 0 then return 1 end
  if not comp(ary[1], x) then return 1 end
  if comp(ary[num], x) then return num + 1 end
  local min, max = 1, num
  while 1 < max - min do
    local mid = mfl((min + max) / 2)
    if comp(ary[mid], x) then
      min = mid
    else
      max = mid
    end
  end
  return max
end

local n, d, a = io.read("*n", "*n", "*n")
d = d * 2
local t = {}
local imos = {}
for i = 1, n do
  t[i] = {io.read("*n", "*n")}
  imos[i] = 0
end
imos[n + 1] = 0
table.sort(t, function(a, b) return a[1] < b[1] end)
local ret = 0
for i = 1, n do
  local x, h = t[i][1], t[i][2]
  if 1 < i then
    imos[i] = imos[i] + imos[i - 1]
  end
  h = h + imos[i]
  if 0 < h then
    local use = mce(h / a)
    ret = ret + use
    local dst = lower_bound(t, x + d + 1)
    imos[i + 1] = imos[i + 1] - use * a
    imos[dst] = imos[dst] + use * a
  end
end
print(ret)


Measured memory_bytes: 30328
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <algorithm>
#include <iomanip>

typedef long long ll;
const ll MOD = 1e9 + 7;
const long long INF = 1LL<<60;
const double PI=3.14159265358979323846;
const int NMAX=100005;
using namespace std;


ll pow(ll a, ll b) {
  if (b == 0) {
    return 1;
  } else if (b % 2 == 0) {
    ll d = pow(a, b / 2);
    return (d * d) % MOD;
  } else {
    ll d = pow(a, b - 1);
    return (a * d) % MOD;
  }
}

int main(){
    ll n, k;
    cin >> n >> k;
    vector<pair<ll,bool> > a;
    int negatives = 0;
    for(int i = 0; i < n; i++){
        ll tmp;
        cin >> tmp;
        bool positive = true;
        if(tmp < 0){
            positive = false;
            tmp = abs(tmp);
            negatives++;
            a.push_back(make_pair(tmp, positive));
        } else {
            a.push_back(make_pair(tmp, positive));
        }
    }

    ll ans = 1;
    if(negatives == n && k%2 == 1){
        sort(a.begin(), a.end());
        for(int i = 0; i < k; i++){
            ans *= a[i].first;
            ans %= MOD;
        }
        ans = -ans + MOD;
    } else {
        sort(a.begin(), a.end(), greater<pair<ll,bool> >());
        bool  is_neg = false;
        for(int i = 0; i < k; i++){
            ans *= a[i].first;
            ans %= MOD;
            if(a[i].second == false){
                is_neg = !is_neg;
            }
        }
        if(is_neg == true && n != k){
            ll min_neg = INF;
            ll min_pos = INF;
            ll max_neg = -1;
            ll max_pos = -1;
            for(int i = k-1; i >= 0; i--){
                if(a[i].second == false){
                    min_neg = min(min_neg, a[i].first);
                } else {
                    min_pos = min(min_pos, a[i].first);
                }
            }
            for(int i = k; i < n; i++){
                if(a[i].second == false){
                    max_neg = max(max_neg, a[i].first);
                } else {
                    max_pos = max(max_pos, a[i].first);
                }
            }

            ll adjust;
            if(min_neg == INF || max_pos == -1){
                adjust = pow(min_pos, MOD-2);
                adjust *= max_neg;
                adjust %= MOD;
            } else if(min_pos == INF || max_neg == -1){
                adjust = pow(min_neg, MOD-2);
                adjust *= max_pos;
                adjust %= MOD;
            } else {
                if(min_pos/(long double)max_neg < min_neg/(long double)max_pos){
                    adjust = pow(min_pos, MOD-2);
                    adjust *= max_neg;
                    adjust %= MOD;
                } else {
                    adjust = pow(min_neg, MOD-2);
                    adjust *= max_pos;
                    adjust %= MOD;
                }
            }
            ans *= adjust;
            ans %= MOD;
            is_neg = false;
        }
        if(is_neg == true){
            ans = -ans + MOD;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 7416
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define all(v) (v.begin(), v.end())
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    ll n, m;
    cin >> n >> m;

    ll ans = 0;
    if (m >= 2 * n) ans = n + (m - 2 * n) / 4;
    else ans = m / 2;

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// const int INF = (1 << 30) - 1;
// const ll LL_INF = (1LL << 62) - 1;
// const ll MOD = 1e9 + 7;

int N;
vector<pair<double, double>> xy;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N;
  xy.resize(N);
  for (int i = 0; i < N; i++) {
    double x, y;
    cin >> x >> y;
    xy[i] = make_pair(x, y);
  }
  sort(xy.begin(), xy.end());

  int num = 1;
  for (int i = 1; i <= N; i++) {
    num *= i;
  }

  double ans = 0.0;
  do {
    for (int i = 1; i < N; i++) {
      double x = xy[i - 1].first - xy[i].first;
      double y = xy[i - 1].second - xy[i].second;
      ans += sqrt(x * x + y * y);
    }
  } while (next_permutation(xy.begin(), xy.end()));
  ans /= num;

  cout << fixed << setprecision(10) << ans << endl;
  return 0;
}

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

int main(){
    int a;
    cin >> a;
    int b;
    cin >> b;
    int c = a / b;
    if(a%b != 0)c++;
    cout << c << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector> 
# include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

#define int long long
using namespace std;
const int MX = 1e6;
const int inf = 1e13;
const int mod = 1e9+7;
#define ll long long
signed main() {
    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    rep(i,n-k) {
        if(a[i+k]>a[i]) cout << "Yes" << endl;
        else cout << "No" << endl;
       
    }
  return 0;
}



Measured memory_bytes: 4840
#include<stdio.h> 
int main(void){
  int a,b,c,d,Takahashi;
  scanf("%d",&a);
  scanf("%d",&b);
  scanf("%d",&c);
  scanf("%d",&d);
  
  while(a>0&&c>0){
    c = c - b;
    if(c<=0){
      Takahashi = 1;
      break;
    }
    a = a - d;
    if(a<=0){
      Takahashi = 0;
      break;
    }
  }
  if(Takahashi == 1)
    printf("Yes");
  else
    printf("No");
  return 0;
}

Measured memory_bytes: 1736
'use strict';
let execute = input => {
  const TIME = input.split(' ').map(el => +el);
  let executing = [];
  for (let i = Number(TIME[0]); i < TIME[1]; i++) {
    executing[i] = executing[i] === undefined ? 1 : executing[i] + 1;
  }
  for (let i = Number(TIME[2]); i < TIME[3]; i++) {
    executing[i] = executing[i] === undefined ? 1 : executing[i] + 1;
  }
  let ans = executing.reduce((prev, cur) => {
    return cur === 2 ? prev + 1 : prev;
  }, 0);
  return ans;
};

function Main(input) {
  console.log(execute(input));
}
Main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 11468
#include<stdio.h>

int main(){
  while(1){
	int i,ans = 0;
    char x[1001];
	scanf("%s",x);
	if(x[0] == '0') break;
	for(i = 0; x[i] != '\0'; i++) ans += x[i] - '0';
	printf("%d\n",ans);
  }
  return 0;
}

Measured memory_bytes: 536
#include <iostream>
#include <sstream>
#include <vector>
#include <cassert>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <tuple>
#include <regex>
#include <map>

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

template<class T>
T gcd(T a, T b) {
	return (b == 0) ? a : gcd(b, a % b);
}

template<class T>
T lcm(T a, T b) {
	T h = gcd(a, b);
	return (h != 0) ? (a * (b / h)) : 0;
}


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

	vector<ull> A(N);
	for (ull i = 0; i < N; i++) {
		cin >> A[i];
	}

	const auto ans = accumulate(cbegin(A), cend(A), 1ULL, lcm<ull>);

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int K;
  string S;
  cin >> K;
  cin >> S;
  if(S.size() <= K){
    cout << S << endl;
  } else if(S.size() > K){
    for(int i =0; i < K; i++){
      cout << S.at(i);
    }
    cout <<"..." << endl;
  }
}
  

Measured memory_bytes: 3628
from collections import deque
import sys
readline = sys.stdin.readline
N, Q = map(int, readline().split())
G = [[] for i in range(N)]
C = [0] * N
for i in range(N-1):
    a, b = map(int, readline().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for i in range(Q):
    p, x = map(int, readline().split())
    C[p-1] += x
used = [0]*N
used[0] = 1
que = deque([0])
while que:
    v = que.popleft()
    c = C[v]
    for w in G[v]:
        if used[w]:
            continue
        used[w] = 1
        C[w] += c
        que.append(w)
print(*C)

Measured memory_bytes: 56148
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MAX=1e18;
ll mod=1e9+7;
#define pb push_back
#define se second
#define fi first
#define maxe max_element
#define mine min_element
#define debug(x) cout<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;
#define debug4(x,y,z,w) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\t"<<#w<<" :: "<<w<<endl;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define boost  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
vector<int> graph[205];
int color[205];
int nCk[100][100];
bool bipartite_jugding(int v, int c){
    color[v] = c;
    for(int i = 0; i < graph[v].size(); ++i){
        if(color[graph[v][i]] == c) return false;
        if(color[graph[v][i]] == 0 && !bipartite_jugding(graph[v][i], -c)){
            return false;
        }
    }
    return true;
}

 void combi() {
	for (int i = 0; i <= 99; ++i) nCk[i][0] = 1;
	for (int i = 1; i <= 99; ++i) for (int j = 1; j <= i; ++j) {
		nCk[i][j] = (nCk[i-1][j] + nCk[i-1][j-1]) % mod;
	}
}

long long expo(ll x,ll n,ll M)
{

    if(n==0)
        return 1;
    else if(n%2 == 0)        //n is even
        return expo((x*x)%M,n/2,M);
    else                             //n is odd
        return (x*expo((x*x)%M,(n-1)/2,M))%M;

}
ll n,s;
void solve()
{
    int t=1;
   // cin>>t;
    while(t--)
    {

   cin>>n>>s;
   vector<ll> h(n);ll sum=0;
   for(int i=0;i<n;i++){cin>>h[i];}
  sort(h.begin(),h.end());
  for(int i=0;i<(n-s);i++)
    sum+=h[i];
  cout<<sum<<endl;

   }
}

int main()
{
    boost;
  solve();
}


Measured memory_bytes: 1792
# novel様のコードを借りて提出のテストです。失礼します
def lcs(s1, s2):
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if chr_idx:
                dp.append(chr_idx)
    return len(dp)


n = int(input())
for _ in range(n):
    x = input()
    y = input()
    print(lcs(x, y))


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

const int INF = 9999999;

vector<vector<int>> cost;
int d[1000];
bool used[1000];
int V;

void calc() {
	fill(d, d + V, INF);
	fill(used, used + V, false);
	d[0] = 0;

	while (true) {
		int v = -1;
		for (int u = 0; u < V; u++) {
			if (!used[u] && (v == -1 || d[u] < d[v])) v = u;
		}

		if (v == -1)break;
		used[v] = true;
		for (int u = 0; u < V; u++) {
			d[u] = min(d[u], d[v] + cost[v][u]);
		}
	}
}

int main() {
	int w, h;
	while (cin >> w >> h , w != 0 || h != 0) {
		V = w * h;
		cost = vector<vector<int>>(h * w, vector<int>(h * w, INF));
		for (int i = 0; i < 2 * h - 1; i++) {
			int wall;
			if (i % 2 == 0) {
				for (int j = 0; j < w - 1; j++) {
					cin >> wall;
					if (wall == 0) {
						cost[(i / 2) * w + j][(i / 2) * w + j + 1] = cost[(i / 2) * w + j + 1][(i / 2) * w + j] = 1;
					}
				}
			}
			else {
				for (int j = 0; j < w; j++) {
					cin >> wall;
					if (wall == 0) {
						cost[(i / 2) * w + j][(i / 2 + 1) * w + j] = cost[(i / 2 + 1) * w + j][(i / 2) * w + j] = 1;
					}
				}
			}
		}
		calc();
		int dist = d[h * w - 1];
		if (dist == INF)
			cout << 0 << endl;
		else
			cout << dist + 1 << endl;
	}
}

Measured memory_bytes: 7068
#include<bits/stdc++.h>
#define ll long long

int main(){
	ll a, b;
	scanf("%lld%lld", &a, &b);
	int sit = -1;
	for (int i = 60; ~i; -- i){
		if ((a >> i & 1) != (b >> i & 1)){
			sit = i;
			break;
		}
		else{
			if (a >> i & 1){
				a ^= 1ll << i;
				b ^= 1ll << i;
			}
		}
	}
	if (!~sit){
		return printf("1\n"), 0;
	}
	ll ans = (1ll << sit) - a;
	int sit1 = -1;
	for (int i = sit - 1; ~i; -- i){
		if (b >> i & 1){
			sit1 = i;
			break;
		}
	}
	ll l1 = 1ll << sit, r1 = (1ll << sit) + (1ll << sit1 + 1) - 1;
	ll l2 = 1ll << sit ^ a, r2 = (1ll << sit + 1) - 1;
	ans += r1 - l1 + r2 - l2 + 2;
	if (r1 >= l2){
		ans -= r1 - l2 + 1;
	}
	return printf("%lld\n", ans), 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<math.h>
#include<bitset>
#include<iomanip>
using namespace std;

typedef stack<int> IntStack;
typedef queue<int> IntQueue;

const double pi = 3.141592653589793;

/*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*/



int main()
	
{	
	double r;
	cin >> r;

	cout << fixed << setprecision(5) << pi * r*r << " " << 2 * pi*r;

	return 0;
}



Measured memory_bytes: 3276
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		out=new PrintWriter (new BufferedOutputStream(System.out));
		FastReader s=new FastReader();
		int n=s.nextInt();
		int[] arr=new int[n];
		for(int i=0;i<n;i++) {
			arr[i]=s.nextInt();
		}
		int[] dp=new int[n];
		dp[0]=0;
		dp[1]=Math.abs(arr[1]-arr[0]);
		for(int i=2;i<n;i++) {
			dp[i]=Integer.min(dp[i-1]+Math.abs(arr[i]-arr[i-1]), dp[i-2]+Math.abs(arr[i]-arr[i-2]));
		}
		out.println(dp[n-1]);
		out.close();
	}
	
	public static PrintWriter out;
	
	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;
		//it reads the data about the specified point and divide the data about it ,it is quite fast
		//than using direct 

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());//converts string to integer
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception e) {
				e.printStackTrace();
			}
			return str;
		}
	}

}


Measured memory_bytes: 31780
#coding: UTF-8
import math

N = input()
A = list(map(int, input().split()))
cont = 0

for i,a in enumerate(A):
    if i > 0:
        if a == A[i-1]:
            cont+=1
            if i != int(N) - 1:
                if (a+1) == A[i+1]:
                    A[i] = a+2
                else:
                    A[i] = a+1

print(cont)


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

int main(){
    string S, T;
    cin >> S >> T;

    int ans = 0;
    for(int i = 0; i < 3; i++){
        if(S[i] == T[i]){
            ans++;
        }
    }
    
    cout << ans << endl;

    return 0;

}



Measured memory_bytes: 256
//FIRST THINK THEN CODE.

  #include <bits/stdc++.h>


  using namespace std;

  typedef long long ll;

  #define rep(i,a,b) for(ll i=a;i<b;++i)
  #define rrep(i,a,b) for(ll i=a;i>b;--i)
  #define FOR(i,n)  for(ll i=0;i<n;i++)
  #define vi vector<int>
  #define vl vector<ll>
  #define ld long double
  #define vld vector<ld>
  #define vvi vector<vector<int>>
  #define vvl vector<vector<long long>>
  #define vvld vector<vector<ld>>
  #define pii pair<int,int>
  #define pll pair<long,long>
  #define vpii vector<pii>
  #define vpll vector<pll>
  #define ff first
  #define ss second
  #define pb push_back
  #define pf push_front
  #define mp make_pair
  #define lb lower_bound
  #define ub upper_bound
  #define bs binary_search
  #define d1(x) cout<<(x)<<endl
  #define d2(x,y) cout<<(x)<<" "<<(y)<<endl
  #define d3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
  #define d4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl
  #define PI 3.1415926535897932384626433832795
  #define fix(f,n) fixed<<setprecision(n)<<f
  #define all(x) x.begin(),x.end()
  #define rev(p) reverse(p.begin(),p.end());
  #define endl "\n"
  #define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  #define popcount(x) __builtin_popcountll(x)
  #define sz(x) ((ll)x.size())
  const ll M=1000000007;
  const ll MM=998244353;
  ll begtime = clock();
  #define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";
  //#define _Find_next 
  //#define _Find_first 



  ll newmod(ll a,ll b)
  {
  return ((a%b)+b)%b;
  }


  ll powM(ll a,ll b,ll m )
  { 
  if(a<=0)return 0;
  a%=m;
  if(!b)return 1;
  ll ans=1LL;
  while(b)
  {
  if(b&1)ans=ans*a%m;
  a=a*a%m;
  b>>=1;
  }

  return ans;
  }



  ll poww(ll a,ll b)
  { 

  ll ans=1;
  while(b)
  {
  if(b&1)ans=ans*a;
  a=a*a;
  b>>=1;
  }

  return ans;

  }

  template<typename T,typename F>
  void chmax( T &a,F b){
  if(b>a)a=b;
  }

  template<typename T,typename F>
  void chmin( T &a,F b){
  if(b<a)a=b;
  }

string tostring(ll x){
  stringstream sss;
  sss<<x;
  string ans=sss.str();
  return ans;
}


  const ll N=1e6+5;


//ll val[3005][3005][5];
ll dp[3005][3005][5];
  int main()
  { 

    IOS;

ll r,c;
cin>>r>>c;
ll k;
cin>>k;

vvl val(r+1,vl(c+1));

while(k--){
  ll r1,c1,v;
  cin>>r1>>c1>>v;
  val[r1][c1]=v;
}

for(ll i=1;i<=r;i++){
  for(ll j=1;j<=c;j++){
    if(!val[i][j]){
      for(ll p=0;p<=3;p++){
        chmax(dp[i][j][0],dp[i-1][j][p]);
         chmax(dp[i][j][p],dp[i][j-1][p]);   
      }
    }else{
      for(ll p=0;p<=3;p++){
        chmax(dp[i][j][0],dp[i-1][j][p]);
        chmax(dp[i][j][p],dp[i][j-1][p]);
        chmax(dp[i][j][1],dp[i-1][j][p]+val[i][j]);
        if(p&&dp[i][j-1][p-1])chmax(dp[i][j][p],dp[i][j-1][p-1]+val[i][j]);  
      }
    }
  }
}

ll ans=0;

FOR(i,4){
  chmax(ans,dp[r][c][i]);
}



cout<<ans<<endl;




  return 0;

  }

Measured memory_bytes: 425744
#include<stdio.h>
#include<math.h>
int main() {
    int a, b;
    while (scanf("%d%d", &a, &b) != EOF) {
        int c = a + b;
        int x = floor(log10(c)) + 1;
        printf ("%d\n", x);
    }
    return 0;
}

Measured memory_bytes: 1992
#include <iostream>
#include <string>

using namespace std;

int main(){
    int N, M=0, i, j, m, l, sum=0;
    int a[200000], b[200000];

    cin >> N;
    for (i = 1; i <= N; i++) {
      cin >> a[i];
    }

//i番目の箱にいれる個数を決定
    for (i = N; i > 0; i--) {
      sum = 0;
      m = N / i ;
      for (j = 2; j <= m; j++) {
        sum += b[i*j];
      }  //ここまででiの倍数の書かれた箱に入ってる玉の合計
      sum += a[i]; 
      sum = sum % 2;
      b[i] = sum;
    }

    for (i = 1; i <= N; i++) {
      M += b[i];
    }

    cout << M << '\n';

    for (i = 1; i <= N; i++) {
      if (b[i] == 1) {
        cout << i << " ";
      }
    }

    return 0;
}


Measured memory_bytes: 2432
s = input()
K = int(input())

li = sorted(list(set(s)))
hitList = []

def oneMoreChar(moji):
    hitList.append(moji)
    if len(hitList) < K:
        for i in range(len(li)):
            if moji+li[i] in s:
                return oneMoreChar(moji+li[i])
    else:
        pass

for char in li:
    oneMoreChar(char)

print(hitList[K-1])

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
int comb(int a, int b){
  if(b > a) return 0;
  if(b == 0) return 1;
  return comb(a,b-1)*(a-b+1)/b;
}

signed main(){
  int N, a, b;
  cin >> N >> a >> b;
  vector<long long> V(N);
  for(int i = 0; i < N; ++i) cin >> V[i];
  sort(V.begin(), V.end(),greater<>());
  double m = 0;
  for(int i = 0; i < a; ++i) m += V[i];
  printf("%.12f\n",(m/(double)a));

  int r = a, l = a-1;
  while(r < N && V[r] == V[a-1]) ++r;
  while(l >= 0 && V[l] == V[a-1]) --l;
  //cout << l << " " << r << endl;
  int ans = 0;
  for(int i = a; i <= b; ++i){
    ans += comb(r-l-1,i-l-1);
    if(i < N && V[0] != V[i]) break;
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
  int x, y;
  cin >> x >> y;
  if(y%2 == 1){
    cout << "No" << endl;
    return 0;
  }
  if(2*x > y || 4*x < y){
    cout << "No" << endl;
    return 0;
  }
  cout << "Yes" << endl;
  return 0;
}



Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
int INF = 1000000000;
int main(){
  while (1){
    int N, M;
    cin >> N >> M;
    if (N == 0 && M == 0){
      break;
    }
    vector<vector<tuple<int, int, int>>> E(N);
    for (int i = 0; i < M; i++){
      int u, v, d, c;
      cin >> u >> v >> d >> c;
      u--;
      v--;
      E[u].push_back(make_tuple(d, c, v));
      E[v].push_back(make_tuple(d, c, u));
    }
    vector<int> d(N, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, 0));
    while (!pq.empty()){
      int c = pq.top().first;
      int v = pq.top().second;
      pq.pop();
      if (d[v] == INF){
        d[v] = c;
        for (auto edge : E[v]){
          int w = get<2>(edge);
          if (d[w] == INF){
            pq.push(make_pair(c + get<0>(edge), w));
          }
        }
      }
    }
    vector<pair<int, int>> P(N);
    for (int i = 0; i < N; i++){
      P[i] = make_pair(d[i], i);
    }
    sort(P.begin(), P.end());
    int ans = 0;
    for (int i = 1; i < N; i++){
      int cost = INF;
      for (auto edge : E[P[i].second]){
        int j = get<2>(edge);
        if (P[i].first - d[j] == get<0>(edge)){
          cost = min(cost, get<1>(edge));
        }
      }
      ans += cost;
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 4132
#include <iostream>

using namespace std;

int selectionSort(int A[], int N) {
	int res = 0;
	for (int i = 0; i < N; ++i) {
		int minj = i;
		for (int j = i; j < N; ++j){
			if (A[j] < A[minj]){
			    minj = j;
			}
		}
		if (i != minj){
		    swap(A[i], A[minj]);
		    res++;
		}
	}
	return res;
}

int main() {
	int A[100];
	int N;
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> A[i];
	int ans = selectionSort(A, N);
	for (int i = 0; i < N; ++i) {
		if (i) cout << " ";
		cout << A[i];
	}
	cout << endl << ans << endl;

	return 0;
}


Measured memory_bytes: 3088
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

bool add(vector<ll> &mat,vector<int> &ls,ll s,bool flag){
  int n=mat.size();
  rep(i,n){
    if(ls[i]==-1) continue;
    if(s&(1ll << ls[i])) s^=mat[i];
  }
  if(flag) return s==0;
  ls.push_back(-1);
  per(i,64){
    if(s&(1ll << i)) {
      ls.back()=i;
      break;
    }
  }
  if(ls.back()!=-1){
    rep(i,n){
      if(mat[i]&(1ll << ls.back())) mat[i]^=s;
    }
  }
  mat.push_back(s);
  sort(mat.begin(),mat.end(),[](ll a,ll b){return a>b;});
  sort(ls.begin(),ls.end(),[](ll a,ll b){return a>b;});
  return true;
}


void solve(int n,vector<ll> &a,string &s){
  vector<ll> mat={};vector<int> ls={};
  per(i,n){
    if(s[i]=='0') {
      add(mat,ls,a[i],0);
    }
    else{
      bool flag=add(mat,ls,a[i],1);
      if(!flag) {
        cout << 1 << endl;
        return;
      }
    }
  }
  cout << 0 << endl;
}

int main(){
  int t;
  cin >> t;
  rep(i,t){
    int n;cin >> n;vector<ll> a(n);string s;
    rep(i,n){
      cin >> a[i];
    }
    cin >> s;
    solve(n,a,s);
  }
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(50);
}

Measured memory_bytes: 3584
import java.util.Scanner;

public class Main{
  public static int[] correctGoal;
  public static int[] wrongGoal;
  
  public static void goal(String s, int start){
    if(s.charAt(start) == 'L'){
      correctGoal[start] = wrongGoal[start - 1];
      wrongGoal[start] = correctGoal[start - 1];
    }else if(start > 0 && s.charAt(start - 1) == 'R'){
      correctGoal[start] = wrongGoal[start - 1];
      wrongGoal[start] = correctGoal[start - 1];
    }else{
      int step = 0;
      while(s.charAt(start + step) == 'R'){
        step++;
      }
      if(step % 2 == 0){
        correctGoal[start] = start + step;
        wrongGoal[start] = start + step - 1;
      }else{
        correctGoal[start] = start + step - 1;
        wrongGoal[start] = start + step;
      }
    }
  }
  
  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);
    String s = scanner.nextLine();
    int n = s.length();
    correctGoal = new int[n];
    wrongGoal = new int[n];
    int[] gathered = new int[n];
    for(int i = 0; i < n; i++){
      gathered[i] = 0;
      goal(s, i);
    }
    for(int i = 0; i < n; i++){
      gathered[correctGoal[i]]++;
    }
    for(int i = 0; i < n - 1; i++){
      System.out.print(gathered[i] + " ");
    }
    System.out.println(gathered[n-1]);  
  }
}


Measured memory_bytes: 48984
import itertools
N, M, Q = list(map(int, input().split()))
a = []
b = []
c = []
d = []

for i in range(Q):
  aa, bb, cc, dd = list(map(int, input().split()))
  a.append(aa)
  b.append(bb)
  c.append(cc)
  d.append(dd)

Ms = [i for i in range(1, M+1)]


res = 0
for s in itertools.combinations_with_replacement(Ms, N):
  sum_ = 0
  for j in range(Q):
    if s[b[j]-1] - s[a[j]-1] == c[j]:
      sum_ += d[j]
  if sum_ > res:
    res = sum_

print(res)

Measured memory_bytes: 9232
#include <cstdio>
#include <functional>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>

#define INF (1ll<<60)
#define MOD 1000000007
#define BOUND 27182818284

typedef long long ll;
typedef long long int lli;

#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)

template<class T>bool umax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool umin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using namespace std;

// gcd
int gcd(int a, int b){
    if(a==0)
        return b;
    return gcd(b%a,a);
}
// gcd array
int findGCD(int arr[], int n){
    int result = arr[0];
    for (int i=1; i < n; i++)
        result = gcd(arr[i], result);

    return result;
}

// sort big to small
// sort(A,A+N, greater<int>());

// v.front() = -BOUND;
// v.back() = BOUND;

// Iterator
// v.begin
// v.end

int main() {
    long long ans[87];
    int N;
    cin >> N;

    ans[0]=2;
    ans[1]=1;
    for(int i=2; i<=N; i++){
        ans[i]=ans[i-1]+ans[i-2];
    }

    cout << ans[N] << endl;
    return 0;
}



Measured memory_bytes: 256
use bigint;

my $N = <STDIN>;
my ($x, $y) = (1, 1);
for (1..$N) {
    my $line = <STDIN>; chomp $line;
    my ($p, $q) = split(/ /, $line);
    # say sprintf('(%d, %d) <- (%d, %d)', $x, $y, $p, $q);

    my $xx = int(($x + $p - 1) / $p) * $p;
    my $xy = ($xx / $p) * $q;
    # say sprintf("\t(%d, %d)", $xx, $xy);

    my $yy = int(($y + $q - 1) / $q) * $q;
    my $yx = ($yy / $q) * $p;
    # say sprintf("\t(%d, %d)", $yx, $yy);

    my $x_meet = ($xx >= $x) && ($xy >= $y);
    my $y_meet = ($yx >= $x) && ($yy >= $y);

    if ($x_meet && $y_meet) {
        if ($xx + $xy < $yy + $yx) {
            ($x, $y) = ($xx, $xy);
        } else {
            ($x, $y) = ($yx, $yy);
        }
    } elsif ($x_meet) {
        ($x, $y) = ($xx, $xy);
    } elsif ($y_meet) {
        ($x, $y) = ($yx, $yy);
    } else {
        die 'oops';
    }
}
# say sprintf('(%d, %d)', $x, $y);
print $x + $y;

Measured memory_bytes: 4864
#include<stdio.h>
#include<string.h>
  char ha[1<<21],k[256];
int main(int argc,char *argv[]){
  int flg;
  int val,s,t;
  char c;
  k['T'] = 1;
  k['G'] = 2;
  k['C'] = 3;
  k['A'] = 4;
  
  scanf("%d", &val);
  getchar();
  while (val--) {
    s = 0;
    t = 1;
    flg = ( c = getchar() ) == 'i';
    while ( ( c = getchar() ) != ' ' );
    while ( ( c = k[getchar()] ) != 0 ) {
      s += c * t;
      t *= 4;
    }
    if (flg) ha[s] = 1; else puts( ha[s] ? "yes" : "no" );
  }
  return 0;
}

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

int main(){
    int S,h,m,s;
    0 <= S < 86400;
    cin >> S;
    h = S/3600;
    m = (S%3600)/60;
    s = (S%3600)%60;
    cout << h << ":" << m <<":"<< s <<endl;
    return 0;
}


Measured memory_bytes: 3120
#include<bits/stdc++.h>
using namespace std;
template<typename T>void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)
    putchar(x+'0');
    else
    {
        print(x/10);
        putchar(x%10+'0');
    }
}
int count(char c,string s)
{
	int ans=0;
	for(int i=0;i<s.length();i++)
	{
		if(s[i]==c)ans++;
	}
	return ans;
}
int main()
{
	string s;
	cin>>s;
	cout<<s.length()/2-count('p',s)<<endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)x.size()
#define int ll

const int N = 2e5 + 10;
int a[N], dp[N], nxt[N];

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
  	cin >> a[i];
  }
  vector<pair<int, int>> st;
  int ans = 0;
  for (int i = n; i >= 1; i--) {
  	while (!st.empty() && st.back().F > a[i]) {
  		st.pop_back();
  	}
  	if (!st.empty()) {
  		nxt[i] = st.back().S;
  	}
  	st.pb({a[i], i});
  	if (nxt[i] == 0) {
  		dp[i] = (n - i + 1) * a[i];
  	}
  	else {
  		dp[i] = (nxt[i] - i) * a[i] + dp[nxt[i]];
  	}
  	ans += dp[i];
  }
  cout << ans << '\n';
}

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

const int N = 1e6 + 100, M = 55;

typedef long long LL;

int cnt[N];
LL last[N];
LL nck[M][M];
LL pre[M];

int main() {
    // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);


    nck[0][0] = 1;
    for(int i = 1; i < M; i++) {
        nck[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            nck[i][j] = nck[i-1][j-1] + nck[i-1][j];
        }
    }

    int n, K;
    cin >> n >> K;

    for(int i = 0; i < M; i++) {
        for(int j = 1; j <= min(i, K); j++) {
            pre[i] += nck[i][j];
        }
    }

    int And, Or;
    cin >> And >> Or;
    vector<int> bad(n), A(n);
    for(int i = 0; i < n; i++) cin >> A[i];
    vector<int> bits;
    for(int i = 0; i < 18; i++) {
        int b0 = (And>>i)&1, b1 = (Or>>i)&1;
        if(b0 == 1 && b1 == 0) {
            cout << "0" << endl;
            exit(0);
        }
        if(b0 == 0 && b1 == 0) {
            for(int j = 0; j < n; j++) {
                if((A[j]>>i)&1) {
                    bad[j] = true;
                }
            }
        }
        else if(b0 == 1 && b1 == 1) {
            for(int j = 0; j < n; j++) {
                if((A[j]>>i)&1) {}
                else {
                    bad[j] = true;
                }
            }
        }
        else {
            bits.push_back(i);
        }
    }
    vector<int> good;
    for(int i = 0; i < n; i++) {
        if(!bad[i]) good.push_back(A[i]);
    }
    if(good.size() == 0) {
        cout << "0" << endl;
        exit(0);
    }
    int sz = bits.size();
    vector<LL> bad_cnt(1<<sz);
    for(int mask = 0; mask < (1<<sz); mask++) {
        int mm = 0;
        for(int k = 0; k < sz; k++) {
            if((mask>>k) & 1) {
                mm |= (1<<bits[k]);
            }
        }
        for(int i = 0; i < good.size(); i++) {
            int x = good[i]&mm;
            last[x]++;
        }
        for(int i = 0; i < good.size(); i++) {
            int x = good[i]&mm;
            if(last[x] == 0) continue;
            bad_cnt[mask] += pre[last[x]];
            last[x] = 0;
        }
    }
    LL ans = 0;
    for(int mask = 0; mask < (1<<sz); mask++) {
        int popcnt = __builtin_popcount(mask);
        if(popcnt&1) ans -= bad_cnt[mask];
        else ans += bad_cnt[mask];
    }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 7412
#include <stdio.h>
int main(void){
    // Your code here!
    int n,i;
    scanf("%d",&n);
    int a[n],big=0,sum=0;
    for(i=0;i<n;i++){
        scanf("%d", &a[i]);
        if(big<a[i])
        big = a[i];
        sum+=a[i];
    }
    //printf("%d %d",big,sum);
    (big<sum-big) ? printf("Yes") : printf("No") ;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using ll = long long ;

ll comb_tbl[52][52] ={0};

void comb(){
    rep(i,51){//nC0 = 1
        comb_tbl[i][0]=1;//nC0=1
        comb_tbl[i][i]=1;//nCn=1
    }

    rep(i,51){
        reps(j,1,i+1){
            comb_tbl[i][j] = comb_tbl[i-1][j-1] + comb_tbl[i-1][j];
        }
    }

    
}

int main(){
    comb();
    int n,p;
    int e=0,o=0;
    int count = 0;
    cin >> n >> p;
    int a;
    ll ans=0,tot_odd=0,tot_even=0;

    rep(i,n){ 
        cin >> a;
        if(a % 2== 0) e++;
        else o++;
    }

    if(p == 0){
        rep(i,e+1){
            tot_even += comb_tbl[e][i];
        }
        if(o > 0){
            if(o % 2 == 0){//奇数の数が　偶数
                rep(i,o/2+1){//0,2
                    tot_odd += comb_tbl[o][i*2];
                }
            }else{
                rep(i,o/2+1){//1,3,5
                    tot_odd += comb_tbl[o][i*2+1];
                }
            }
        }else{
            tot_odd = 1;
        }
        ans = tot_even * tot_odd;
    }else{//p=1の時 奇数にする
        rep(i,e+1){
            tot_even += comb_tbl[e][i];//eCeまで
        }
        //奇数：1,3,5..と残るようにする
        if(o > 0){
            if(o % 2 == 1){//奇数の数が　偶数
                rep(i,o/2+1){//0,2
                    tot_odd += comb_tbl[o][i*2];
                }
            }else{
                rep(i,o/2+1){//1,3,5
                    tot_odd += comb_tbl[o][i*2+1];
                }
            }
        }else{
            tot_odd = 0;
        }
        ans = tot_even * tot_odd;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#pragma region header
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cctype>
#include <assert.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>
#include <cstring>
#include <array>
// ===============================================================
//using系
#pragma region header
using namespace std;
using lint = long long;
using ld = long double;
using ulint = unsigned long long;
const int dx[] = { 1,0,-1,0 };
const int dy[] = { 0,1,0,-1 };
constexpr lint mod = 1000000007;
constexpr long double pi = 3.141592653589793238462643383279;
#pragma endregion
// ========================================================================
//define
#define INF (lint)10000000000000000;
#define mod (int)1000000007
#pragma region header
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
#pragma endregion
#pragma endregion

int h, w;
vector<vector<int>> d;
vector<vector<int>> memo(10, vector<int>(10));
void input() {
	cin >> h >> w;
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			cin >> memo[i][j];
	d.resize(h);
	for (int i = 0; i < h; i++) {
		d[i].resize(w);
		for (int j = 0; j < w; j++)
			cin >> d[i][j];
	}
	return;
}
void wf() {
	for (int i = 0; i < 10; i++)
		memo[i][i] = 0;
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			for (int k = 0; k < 10; k++)
				memo[j][k] = min(memo[j][k], memo[j][i] + memo[i][k]);
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	input();
	wf();
	lint ans = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (d[i][j] == -1) continue;
			ans += memo[d[i][j]][1];
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3808
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(ll i=(ll)(j);i<(ll)(n);i++)
using ll=int64_t;
#define ALL(a) (a).begin(),(a).end()
#define mp make_pair
ll MOD=1e9+7;
using vi=vector<ll>;
ll N,M,X,Y,Z,y,z,K;
vi p;
ll r(ll X){
    if(p[X]==X) return X;
    return p[X]=r(p[X]);    
}
bool s(ll X,ll Y){
    return r(X)==r(Y);
}
void u(ll X,ll Y){
    X=r(X);
    Y=r(Y);
    if(X!=Y)p[X]=Y;
}
ll mo(ll a,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*a%MOD;
        a=a*a%MOD;
        n/=2;
    }
    return res;
}
int main(){
    cin>>N>>M>>K;
    p.resize(N);
    vector<tuple<ll,ll,ll>> e(M);
    rep(i,0,M){
      	cin>>X>>Y>>Z;
        e[i]=make_tuple(Z,X,Y);
    }
    sort(ALL(e));
    vi m(M);
    rep(i,0,M){
      	tie(m[i],y,z)=e[i];
        rep(i,0,N)p[i]=i;
        u(z-1,y-1);
        rep(j,0,M){
          	tie(Z,X,Y)=e[j];
            if(!s(X-1,Y-1)){
                m[i]+=Z;
                u(X-1,Y-1);
            }
        }
    }
    sort(ALL(m));
    ll a=0;
    rep(i,1,M)if(m[i]==K)a+=mo(2,M-i);
    cout<<a%MOD;
}


Measured memory_bytes: 3704