akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
string str;
char lst;
long long k,ans,cnt;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>str>>k;
    int len=str.length();
    if(len==1){
	printf("%lld\n",k/2);
	return 0;
    }
    lst=str[0];cnt=1;
    for(int i=1;i<len;i++){
	if(str[i]==lst)cnt++;
	else ans+=k*(cnt/2),cnt=1,lst=str[i];
    }
    ans+=k*(cnt/2);
    if(str[len-1]==str[0]){
	int cnts=0,cntt=0;
	for(int i=0;i<len;i++){
	    if(str[i]==str[0])cnts++;
	    else break;
	}
	for(int i=len-1;i>=0;i--){
	    if(str[i]==str[len-1])cntt++;
	    else break;
	}
	if(cnts==len){
	    printf("%lld\n",len*k/2);
	    return 0;
	}
	if(cnts%2&&cntt%2)ans+=(k-1);
    }
    if(str[len-1]==str[0]&&str[len-2]!=str[len-1])ans+=(k-1);
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char c = sc.next().toCharArray()[0];
		switch (c) {
			case 'a':
			case 'e':
			case 'i':
			case 'o':
			case 'u':
				System.out.println("vowel");
				break;
				default:System.out.println("consonant");
		}
	}
}

Measured memory_bytes: 21840
package main

import (
        "fmt"
)

func solution(n int) int {
        sum := 0
        for i := 1; i <= n; i++ {
                switch {
                case i%3 == 0 && i%5 == 0:
                        // "FizzBuzz"
                case i%3 == 0:
                        // "Fizz"
                case i%5 == 0:
                        // "Buzz"
                default:
                        sum += i
                }
        }
        return sum
}

func main() {
        var n int
        fmt.Scan(&n)
        fmt.Println(solution(n))
}

Measured memory_bytes: 1752
local n, a, b, c, d = io.read("*n", "*n", "*n", "*n", "*n")
local len, n1 = math.abs(a - b), n - 1
local isok = false
for i = 0, n1 do
  local l, r = i * c - (n1 - i) * d, i * d - (n1 - i) * c
  if l <= len and len <= r then isok = true break end
end
print(isok and "YES" or "NO")


Measured memory_bytes: 376
#include <iostream>
#include <vector>
#include <math.h>

int main(){

  int N;
  scanf("%d",&N);
  if (N%2==0){
    printf("0.5\n");
  } else {
    printf("%lf\n",(double)(N+1)/(2*N));
  }
  return 0;
}

Measured memory_bytes: 888
#include <iostream>

using namespace std;
int main() {
    int N,M;
    cin >> N >> M;
    int answer = 0;

    // NN
    answer += N * (N-1) / 2;
    // MM
    answer += M * (M-1) / 2;

    cout << answer << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define ll long long
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n){
        cin >> a[i];
    }
    vector<int> left(n), right(n);
    left[0] = a[0];
    right[n-1] = a[n - 1];
    rep(i,n-1){
        left[i + 1] = __gcd(left[i], a[i + 1]);
        right[n - 2 - i] = __gcd(right[n - 1 - i], a[n - 2 - i]);
    }
    int ans = 1;
    rep(i,n){
        if(i==0 || i == n-1){
            ans = max(ans, left[n - 2]);
            ans = max(ans, right[1]);
        }else{
            int g = __gcd(left[i - 1], right[i + 1]);
            ans = max(ans, g);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1408
#include<iostream>
#include<string>
using namespace std;
int main(){
	for(;;){
		int H,W;
		cin>>H>>W;
		if(H==0&&W==0)break;
		else{
			for(int a=0;a<H;a++){
				if(a==0||a==H-1){
					for(int b=0;b<W;b++){
						cout<<"#";
					}
				}else{
					cout<<"#";
					for(int c=2;c<W;c++){
						cout<<".";
					}
					cout<<"#";
				}
				cout<<endl;
			}
			cout<<endl;
		}
	}
}



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

int Num2(int n){
    int counter = 0;
    while(n%2 == 0){
        counter ++;
        n = n/2;
    }
    return counter;
}

int main(){
    int N;
    cin >> N;
    int tempMax=1;
    int tempNum = 0;
    for(int i =1; i <= N; i++){
        if(Num2(i)>tempNum){
            tempNum = Num2(i);
            tempMax = i;
        }
    }
    cout << tempMax << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>
#define MOD 10007
using namespace std;

int n;
long long dp[1111][8];
string s;
map <char, int> shift;

long long rec(int idx, int prev){
  
  if(idx == n) return 1;
  if(dp[idx][prev]) return dp[idx][prev];

  long long ret = 0;
  int sft = shift[s[idx]];
  for(int i = 1; i < 8; i++){
    if((i >> sft & 1) && (i & prev)){
      ret += rec(idx + 1, i) % MOD;
    }
  }
  return dp[idx][prev] = ret;
}

int main(){
  
  shift['I'] = 0, shift['O'] = 1, shift['J'] = 2;
  cin >> n >> s;
  cout << rec(0, 4) % MOD << endl;
}

Measured memory_bytes: 1360
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
int a, b, x, y;
scanf("%d%d%d%d", &a, &b, &x, &y);
printf("%lf %d\n", double(a)*double(b) / 2, x + x == a&&y + y == b);
}


Measured memory_bytes: 128
#include<cstdio> 
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define fo(i,j,k) for(i=j;i<=k;i++)
#define fd(i,j,k) for(i=j;i>=k;i--)
#define cmax(a,b) (a=(a>b)?a:b)
#define cmin(a,b) (a=(a<b)?a:b)
typedef long long ll;
const int N=1e6+5,M=2e6+5,mo=998244353;
int fa[N],n,H,A,B,C,D,i,pp,pd[N],chu[N],ru[N],l,r,act[N];
int get(int x)
{
	if (fa[x]==x) return x;
	return fa[x]=get(fa[x]);
}
int main()
{
	scanf("%d %d\n",&n,&H);
	fo(i,0,H*2) fa[i]=i;
	fo(i,1,n)
	{
		scanf("%d %d %d %d",&A,&B,&C,&D);
		if (!C) l=A;else l=-C; 
		if (!D) r=-B;else r=D;
		l+=H;
		r+=H;
		//e=(l,r)
		act[l]=act[r]=1;
		chu[l]++;
		ru[r]++;
		fa[get(l)]=get(r);
	}
	pp=1;
	// neg: in>=out
	fo(i,0,H) if (ru[i]<chu[i]) pp=0;
	// pos: in<=out
	fo(i,H+1,2*H) if (ru[i]>chu[i]) pp=0;
	fo(i,0,2*H) pd[get(i)]|=(ru[i]!=chu[i]);
	pd[H]=1;
	fo(i,0,2*H) if (act[i]&&!pd[get(i)]) pp=0;
	if (pp) printf("YES");else
	printf("NO");
}

Measured memory_bytes: 8320
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <unordered_map>
#include <map>

#define ll long long int
#define mod 1000000007

using namespace std;


int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    
    int n, k, c;
    cin >> n >> k >> c;
    string s;
    cin >> s;
    
    vector<int> vec;
    vector<int> vec1;
    for(int i = 0; i < s.length(); i++){
        if(s[i] == 'o'){
        vec.push_back(i+1);
        i += c ;
       
        }
       
    }
    
    for(int i = s.length() - 1; i >= 0; i--){
        if(s[i] == 'o'){
        vec1.push_back(i+1);
        i -= c ;
       
        }
       
    }
    
    for(int i = 0; i< k; i++){
        if(vec[i] == vec1[k - i -1]){
            cout << vec[i] <<'\n';
        }
    }
}









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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

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

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.141592653589793238462643383279;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

ll N, A[3], B[3];
ll ans = 0;

int main(void){
    cin >> N; REP(i,3) cin >> A[i]; REP(i,3) cin >> B[i];

    VL dp(N+1,0);
    REP(i,N){
        REP(j,3){
            chmax(dp[i+1], dp[i]);
            if(i+A[j] <= N) chmax(dp[i+A[j]], dp[i]+B[j]-A[j]);
        }
    }

    ll M = N + dp[N];
    VL dp2(M+1, 0);

    REP(i,M){
        chmax(dp2[i+1], dp2[i]);
        REP(j,3) if(i+B[j] <= M) chmax(dp2[i+B[j]], dp2[i]+A[j]-B[j]);
    }

    cout << M+dp2[M] << endl;
    return 0;
}

Measured memory_bytes: 195584
//minamoto
#include<bits/stdc++.h>
#define R register
#define fi first
#define se second
#define pb emplace_back
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
typedef pair<int,int> pi;
const int N=2e5+5,inf=0x3f3f3f3f;
int a[N],b[N],c[N],d[N],f[N];
int n,Q,tot;
priority_queue<pi,vector<pi>,greater<pi> >h;
priority_queue<pi>q;
vector<int>li[N],ri[N];
inline void chg(R int x,R int y){for(;x<=n+1;x+=x&-x)d[x]+=y;}
inline int query(R int x){R int res=0;for(;x;x-=x&-x)res+=d[x];return res;}
int main(){
//	freopen("testdata.in","r",stdin);
	scanf("%d",&n);
	fp(i,1,n)scanf("%d%d",&a[i],&b[i]);
	fp(i,1,n+1)scanf("%d",&c[i]);
	sort(c+1,c+n+1+1);
	fp(i,1,n){
		a[i]=lower_bound(c+1,c+n+1+1,a[i])-c;
		b[i]=lower_bound(c+1,c+n+1+1,b[i])-c;
	}
	fp(i,1,n+1)chg(i,-1);fp(i,1,n)chg(a[i],1);
	fp(i,1,n)if(b[i]<a[i])ri[a[i]-1].pb(b[i]);
	fd(i,n+1,0){
		for(auto v:ri[i])h.push(pi(v,i));
		while(query(i)<-1){
			if(h.empty()||h.top().fi>i){tot=inf;break;}
			chg(h.top().fi,1),chg(h.top().se+1,-1),h.pop(),++tot;
		}
		if(tot>=inf){
			scanf("%d",&Q);
			fp(i,1,Q)puts("-1");
			return 0;
		}
	}
	while(!h.empty())li[h.top().fi].pb(h.top().se),h.pop();
	fp(i,0,n+1){
		for(auto v:li[i])q.push(pi(v,i));
		while(query(i)<0){
			if(q.empty()||q.top().fi<i){tot=inf;break;}
			chg(q.top().se,1),chg(q.top().fi+1,-1),q.pop(),++tot;
		}
		f[i]=tot;
		if(tot>=inf){
			fp(k,i,n+1)f[k]=inf;
			break;
		}
	}
	scanf("%d",&Q);
	for(R int d,e,res;Q;--Q){
		scanf("%d%d",&d,&e);
		d=lower_bound(c+1,c+n+1+1,d)-c;
		e=lower_bound(c+1,c+n+1+1,e)-c;
		res=-1,cmax(res,n+1-f[d-1]),cmax(res,n-f[e-1]);
		printf("%d\n",res);
	}
	return 0;
}

Measured memory_bytes: 20464
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var line = Console.ReadLine().Split(' ').Select(x => int.Parse(x));
            var a = line.ElementAt(0);
            var b = line.ElementAt(1);
            var result = 1 + (int)Math.Ceiling((b - a) / (a - 1.0));
            Console.WriteLine(result);
        }
    }
}


Measured memory_bytes: 11220
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<numeric>
#include<limits>
#include<iterator>
#include<iterator>

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i,n) for(int i=0; i<n; i++)
#define INF (1<<20)

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ll, char> plc;

ll gcd(ll a, ll b) {
	while (b != 0) {
		a = a % b;
		swap(a, b);
	}
	return a;
}

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

	ll g = gcd(abs(a - c), abs(b - d));
	if (g != 1) {
		ll num1 = abs(a - c) / g;
		ll num2 = abs(b - d) / g;
		cout << (num1 + num2 - 1)*g << endl;
	}
	else
		cout << abs(a - c) / g + abs(b - d) - 1 << endl;
	return 0;
}

Measured memory_bytes: 256
n,m,k=map(int,input().split())
BAD=[0 for i in range(n+1)]

E=[]
for inp in range(m):
    a,b=map(int,input().split())
    E.append((a,b))
    BAD[a]-=1
    BAD[b]-=1

B=[] 
for inp in range(k):
    a,b=map(int,input().split())
    B.append((a,b))
    
uf=[i for i in range(n+1)]
def uf_find(x,uf=uf):
    while uf[x]!=x:
        x=uf[x]
    return x       


res=[]

for ele in E:
    if uf_find(ele[0]) == uf_find(ele[1]):
        continue
    else:
        res.append((ele[0],ele[1])) #write result
        
        if uf_find(ele[0])>uf_find(ele[1]):
            uf[uf_find(ele[0])]=uf_find(ele[1])
        else:
            uf[uf_find(ele[1])]=uf_find(ele[0])

SCO=[0 for i in range(n+1)]
for i in range(1,n+1):
    SCO[uf_find(i)]+=1


for bl in B:
    if uf_find(bl[0])==uf_find(bl[1]):
        BAD[bl[0]]-=1
        BAD[bl[1]]-=1

ANS=[str(SCO[uf_find(i)] + BAD[i] -1) for i in range(1,n+1)]
print(" ".join(ANS))
        


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

#define ll long long
#define all(x) (x).begin(), (x).end()
const long long INF = 1LL << 60;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)  //(i, 10) i=0～i=9まで
#define repr(i, n) for (int i = n; i >= 0; i--)   // (i, 10) i=10～i=0まで
#define FOR(i, m, n) for (int i = m; i < n; i++)  // (i, 3, 10) i=3～i=9まで

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;

int mod10(int a) { return a % 10; }
int top(int a) {
    // if (mod10(a) == 0) return a;
    // return (a / 10 + 1) * 10;
    return ((a + 9) / 10) * 10;
}

int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    // cout << fixed << setprecision(5);

    // int a, b, c, d, e;
    // cin >> a >> b >> c >> d >> e;

    // 入力
    int a[5];
    rep(i, 5) cin >> a[i];
    //余りを入れる
    int b[5];
    rep(i, 5) b[i] = mod10(a[i]);

    int j = 200;  //一つの商品の制約以上の数を番兵にする
                  // （問題文の制約より123を超える数値）
    //余りが一番低い数を検索
    rep(i, 5) {
        if (b[i] != 0) {
            j = min(j, b[i]);
        }
    }

    //余りの最小値が見つからなかったら10にセット
    if (j > 10) {
        j = 10;
    }
    int total = 0;
    rep(i, 5) { total += top(a[i]); }
    // 10を引いて、見つかった最小の余りjを足す。
    total = total - 10 + j;
    cout << total << endl;

    return 0;
}


Measured memory_bytes: 256
/*Jai Bhole Nath */
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
#define int long long int
#define f(i,a,n)    for(int i = a; i < (n); ++i)
#define fe(i, a, n)  for(int i = a; i <= (n); ++i)
#define fr(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define input(arr,n) for(int i=0;i<n;i++) cin>>arr[i];
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define mod 1000000007
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MAX 100
int countWays(vector<int>arr, int m, int N) 
{ 
    ll count[N + 1]; 
    memset(count, (ll)0, sizeof(count)); 
      
    // base case 
    count[0]=1;
      for (ll i = 1; i <= N; i++) 
        for (ll j = 0; j < m; j++) 
  
            if (i >= arr[j]) {
                count[i] += count[i - arr[j]]; 
                count[i]=(count[i]+mod)%mod;
            }

      
    // required number of ways  
    return count[N]%mod; 
      
} 

void solve()
{
	int n,x,y;cin>>n;
	vector<int>arr,arr1;
	for(int i=0;i<n;i++){
		cin>>x>>y;
		arr.pb(x+y);
		arr1.pb(x-y);

	}
	sort(arr.begin(),arr.end());
	sort(arr1.begin(),arr1.end());
	int r=max ((arr[arr.size()-1])-arr[0], (arr1[arr1.size()-1])-arr1[0]);
	cout<<r<<endl;
	


}

signed main()
{
    FIO;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t=1;
    //cin >> t;
    while(t--)
        solve();
    return 0;
}



Measured memory_bytes: 6688
x1, y1, x2, y2 = list(map(int, input().split()))

xx = x2 - x1
yy = y2 - y1

x3 = x2 - yy
y3 = y2 + xx
x4 = x3 - xx
y4 = y3 - yy

print(x3, y3, x4, y4)

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

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

  ll hundred = 1;

  rep(i, d) hundred *= 100;
  if(n<=99){
    cout << hundred * n;
  }
  else
  {
    cout << hundred * 101;
  }


}


Measured memory_bytes: 3632
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<iterator>
#include<complex>
#include<stack>
#include "stdio.h"
using namespace std;

#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)

using ll = long long;
using Pii = pair<int, int>;

const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const long long mod_const = 1e9+7;

int dy[] = { 0, 0, 1, -1, 0 };
int dx[] = { 1, -1, 0, 0, 0 };

using MIte = multimap<ll, ll, greater<ll> >::iterator;

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

	// long long?
	ll N, K;
	cin >> N >> K;

	vector<int> vH(N,0);
	rep(i, N) {
		cin >> vH[i];
	}

	vector<int> dp(N, inf);
	dp[0] = 0;
	rep(i, N) {
		for (int k = 1; k <= K; ++k) {
			if (i + k < N) {
				dp[i + k] = min(dp[i + k], dp[i] + abs(vH[i] - vH[i + k]));
			}
		}
	}

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

	return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<stdio.h>//printf("%.*f\n",*********);
#include<vector>//s.erase(n),vector
#include<algorithm>//next_permutation
#include<set>
#include<string>//char('a'=32+'A')
                //to_string,string,substr
#include<sstream>
#include<complex>
#include<time.h>
#include<random>
#include<cmath>//min,max
#include<math.h>
#include<queue>
#include<time.h>
#include<iomanip>
#include<locale>
#include<utility>//swap

#define rt "\n"
#define rep(i,n) for(int i=0;i<n;i++)
#define rop(i,n) for(int i=1;i<=n;i++)//start==1
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define drop(i,n) for(int i=n;0<i;i--)//end==1
#define yes(ans) if(ans)cout<<"yes"<<rt;else cout<<"no"<<rt;
#define Yes(ans) if(ans)cout<<"Yes"<<rt;else cout<<"No"<<rt;
#define YES(ans) if(ans)cout<<"YES"<<rt;else cout<<"NO"<<rt;
#define Yay(ans) if(ans)cout<<"Yay!"<<rt;else cout<<":("<<rt;
#define sec(a,b,ans) if(ans)cout<<a<<rt;else cout<<b<<rt;
#define vcin(a,n) rep(i,n)cin>>a[i];//vcin(配列名),(繰り返し回数)
#define sort(s) sort(s.begin(),s.end())//昇順
#define reve(s) reverse(s.begin(),s.end())//反転
#define please return
#define AC 0
#define rapid_pleaseAC_fast cin.tie(0);ios::sync_with_stdio(false)
#define pi 3.1415926535897932384626//pi
#define nine 1000000000//10^9

using namespace std;
typedef vector<int> vint;
typedef long double ldouble;
typedef vector<string> vstr;
typedef vector<char> vchar;
typedef vector<double> vdou;
typedef vector<double> vdouble;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<char>> vvchar;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<string>> vvstr;
typedef vector<vector<bool>> vvbool;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool;

long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

long long LCM(long long a, long long b) {
	return a * b / GCD(a, b);
}

unsigned GetDigit(unsigned num) {
	return std::to_string(num).length();
}

int tow(int n) {//2のn乗
	if (n == 0)return 1;
	int x = tow(n / 2);
	x *= x;
	if (n % 2 == 1)x *= 2;
	return x;//@domino
}

int KETA(int n) { //Sum of Each Digit
	int sum = 0;
	while (n > 0) {
		sum += n % 10; n /= 10;
	}
	return sum;
}

unsigned ND(unsigned num) {//Number of Digits
	return std::to_string(num).length();//outmax=10
}

bool KIBN(string s) {
	rep(i, s.size() / 2) {
		if (s[i] != s[s.size() - 1 - i])return false;
	}
	return true;
}

/*

 (char)toupper(a[n])=文字列のn文字目を大文字で出力

  pow(a,b)=aのb乗

  */

int main(void) {
	rapid_pleaseAC_fast;

	int a, b, c;
	cin >> a >> b >> c;
	Yes(a == b && b == c);

	please AC;
}
//参考：---

Measured memory_bytes: 256
use whiteread::parse_line;

fn calc(i: usize, k: usize, h: usize, w: usize, map: &mut Vec<Vec<char>>) {
    let mut cnt = 0;
    if i > 0 {
        if map[i - 1][k] == '#' {
            cnt += 1;
        }
    }
    if k > 0 {
        if map[i][k - 1] == '#' {
            cnt += 1;
        }
    }
    if i < h - 1 {
        if map[i + 1][k] == '#' {
            cnt += 1;
        }
    }
    if k < w - 1 {
        if map[i][k + 1] == '#' {
            cnt += 1;
        }
    }
    if i > 0 && k > 0 {
        if map[i - 1][k - 1] == '#' {
            cnt += 1;
        }
    }
    if i > 0 && k < w - 1 {
        if map[i - 1][k + 1] == '#' {
            cnt += 1;
        }
    }
    if i < h - 1 && k > 0 {
        if map[i + 1][k - 1] == '#' {
            cnt += 1;
        }
    }
    if i < h - 1 && k < w - 1 {
        if map[i + 1][k + 1] == '#' {
            cnt += 1;
        }
    }
    map[i][k] = cnt.to_string().chars().next().unwrap();
}

fn main() {
    let (h, w): (usize, usize) = parse_line().unwrap();
    let mut map: Vec<Vec<char>> = Vec::new();

    for _ in 0..h {
        map.push(parse_line::<String>().unwrap().chars().collect());
    }

    for i in 0..h {
        for k in 0..w {
            if map[i][k] == '.' {
                calc(i, k, h, w, &mut map);
            }
        }
    }
    println!(
        "{}",
        map.iter()
            .map(|x| x.iter().collect::<String>())
            .collect::<Vec<String>>()
            .join("\n")
    );
}


Measured memory_bytes: 2172
a=list(map(int, [input() for i in range(5)]))
b=map(lambda x:(10-(x%10))%10, a)
ans=0
for i in range(5):
    ans+=a[i]
    if (a[i]%10)!=0:
        ans+=10-(a[i]%10)
print(ans-max(b))

Measured memory_bytes: 3316
import java.util.Scanner;

class Main{
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        String a = scan.next();
        String b = scan.next();
        String c = scan.next();
        scan.close();
        if (a.charAt(a.length() - 1) == b.charAt(0) && b.charAt(b.length() - 1) == c.charAt(0))
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}


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

const int inf = 99999999L;

int main() {
    int n; cin >> n;
    vector<int> dp (n, inf);
    vector<int> h;

    for (int i = 0; i < n; ++i) {
        int t; cin >> t;
        h.push_back(t);
    }
    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);
    for (int i = 2; i < n; ++i) {
        dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]),
                    dp[i - 2] + abs(h[i] - h[i - 2]));
    }

    cout << dp[n - 1] << endl;
}


Measured memory_bytes: 1276
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int K; cin >> K;
    cout << ((K + 1) / 2) * (K / 2) << endl;

    return 0;
}


Measured memory_bytes: 3608
// Copyright [2020] <unknown>
#include <bits/stdc++.h>
using namespace std;
// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define dbg(x...) { cerr << "\033[32;1m" << #x << " -> "; err(x); }
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif

#define sz(x) ((int)x.size())

typedef long long LL;


int main(int argc, char const *argv[]) {
    // code
    double t;
    cin >> t;
    t /= 3;
    // cout << t*t*t << endl;
    printf("%.7lf\n", t*t*t);
    return 0;
}


Measured memory_bytes: 256
N = int(input())
nums = list(map(int,input().split()))
x = [0] * N
ans = 0
for i in range(N):
    x[nums[i] - 1] += 1
for i in range(N):
    ans += (x[i]*(x[i]-1))/2
ans = int(ans)    
for i in range(N):
    if x[nums[i] - 1] == 0 or x[nums[i] - 1] ==1:
        print(ans)
    else:
        print(ans - x[nums[i]-1] + 1)

Measured memory_bytes: 81616
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, H: int, W: int, A: "List[int]", B: "List[int]"):
    print([A[i] >= H and B[i] >= W for i in range(N)].count(True))
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, H, W, A, B)

if __name__ == '__main__':
    main()


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

using namespace std;

using ll = long long;

const ll MOD = 1000000007;

const int dx[4] = {+1, 0, -1, 0};
const int dy[4] = {0, -1, 0, +1};

const int DEPTH = 11;
vector<ll> ans;

bool check(vector<int> v, int i, bool lz){
    if(lz) return true;
    if(i == v.back() || (i + 1) == v.back() || (i - 1) == v.back()) return true;
    return false;
}

void dfs(vector<int> v, bool lz){
    if(int(v.size()) >= DEPTH){
        ll res = std::accumulate(v.begin(), v.end(), 0LL, [](ll acc, ll val){
            return 10LL * ll(acc) + ll(val);
        });
        ans.push_back(res);
        return;
    }
    for(int i=0;i<=9;i++){
        if(check(v, i, lz)){
            v.push_back(i);
            if(lz && i == 0) dfs(v, true);
            else dfs(v, false);
            v.pop_back();
        }
    }
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ll k; cin >> k;
    vector<int> s = {0};
    dfs(s, true);
    // cout << ans.size() << endl;
    cout << ans[k] << endl;
}


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

using namespace std;

using int64 = long long;

struct edge
{
  int to, cost;
};

typedef vector< vector< edge > > Graph;

template< typename T = int >
vector< T > Dijkstra(Graph &g, int s)
{
  typedef pair< T, int > Pi;
  vector< T > min_cost(g.size(), numeric_limits< T >::max() / 3);
  priority_queue< Pi, vector< Pi >, greater< Pi > > que;
  que.emplace(0, s);
  min_cost[s] = 0;
  while(!que.empty()) {
    auto p = que.top();
    que.pop();
    if(p.first > min_cost[p.second]) continue;
    for(auto &e : g[p.second]) {
      if(p.first + e.cost >= min_cost[e.to]) continue;
      min_cost[e.to] = p.first + e.cost;
      que.emplace(min_cost[e.to], e.to);
    }
  }
  return (min_cost);
}


int main()
{
  int N, M, A[100000], B[100000], C[100000];

  scanf("%d %d", &N, &M);
  Graph g(N), rg(N), dag(N);
  for(int i = 0; i < M; i++) {
    scanf("%d %d %d", &A[i], &B[i], &C[i]);
    --A[i], --B[i];
    g[A[i]].emplace_back((edge) {B[i], C[i]});
    rg[B[i]].emplace_back((edge) {A[i], C[i]});
  }
  auto latte = Dijkstra< int64 >(g, 0);
  auto malta = Dijkstra< int64 >(rg, 1);
  vector< int > ans(M, -1);
  for(int i = 0; i < M; i++) {
    if(latte[A[i]] + malta[B[i]] + C[i] == latte[1]) {
      dag[A[i]].emplace_back((edge) {B[i], i});
      dag[B[i]].emplace_back((edge) {A[i], i});
    } else if(latte[B[i]] + malta[A[i]] + C[i] < latte[1]) {
      ans[i] = 1;
    } else {
      ans[i] = 0;
    }
  }

  vector< int > dp(N), order(N);
  bool v[100000] = {};
  int ord = 0;
  function< void(int, int) > dfs = [&](int idx, int par)
  {
    v[idx] = true;
    dp[idx] = ord++;
    order[idx] = dp[idx];
    for(auto &e : dag[idx]) {
      if(e.cost == par) continue;
      if(!v[e.to]) dfs(e.to, e.cost), dp[idx] = min(dp[idx], dp[e.to]);
      else dp[idx] = min(dp[idx], order[e.to]);
      if(dp[e.to] <= order[idx]) ans[e.cost] = 0;
    }
  };
  dfs(0, -1);

  for(int i = 0; i < M; i++) {
    if(ans[i] == 0) puts("SOSO");
    else if(ans[i] == 1) puts("HAPPY");
    else puts("SAD");
  }
}

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

using namespace std;

#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) FOR(i, n, 0)
#define MFOR(i, m) for(auto i=(m).begin();i!=(m).end();i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

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

const double eps = 1e-10;
const int MOD = 1000000007;

template<typename T>
void printv(vector<T> const& s) {
  REP(i, s.size()) {
    cout << s[i] << " ";
  }
  cout << endl;
}

struct Sieve {
  vector<bool> isprime;

  void init(size_t max){
    if(max+1 > isprime.size()){     // resizeで要素数が減らないように
        isprime.resize(max+1,true); // IsPrimeに必要な要素数を確保
    }
    isprime[0] = false; // 0は素数ではない
    isprime[1] = false; // 1は素数ではない

    for(size_t i=2; i*i<=max; ++i) // 0からsqrt(max)まで調べる
        if(isprime[i]) // iが素数ならば
            for(size_t j=2; i*j<=max; ++j) // (max以下の)iの倍数は
                isprime[i*j] = false;      // 素数ではない
  }
};


int main () {
  cin.tie(0);
  cout << setprecision(10);

  Sieve s;
  s.init(1000001);
  while(1) {
    int a, d, n; cin >> a >> d >> n;
    if(a == 0 && d == 0 && n == 0) break;
    while(n > 0) {
      if(s.isprime[a]) {
        if(n == 1) {
          cout << a << endl;
          break;
        } else {
          n--;
          a += d;
        }
      } else {
        a += d;
      }
    }
  }
}



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

using namespace std;

const int kMod = 1e9 + 7;

void upd(int& x, int y) {
    x += y;
    if (x >= kMod) 
        x -= kMod;
    if (x < 0)
        x += kMod;
}

int main() {
    string k; cin >> k;
    int n = k.size();

    int d; cin >> d;
    
    
    vector<vector<int>> right(n + 1, vector<int>(d, 0));
    right[n][0] = 1;
    for (int i = n - 1; i >= 0; --i) {
        for (int x = 0; x < 10; ++x) {
            for (int j = 0; j < d; ++j) {
                upd(right[i][(j + x) % d], right[i + 1][j]);
            }
        }    
    }

    int total = 0; upd(total, -1);
   
    vector<int> pw(n + 1, 1);
    for (int i = 0; i < n; ++i)
        pw[i + 1] = pw[i] * 10 % d;

    int have = 0; 
    for (int i = 0; i < n; ++i) {
        for (int d1 = 0; d1 < (k[i] - '0'); ++d1) {
            int r1 = (have + d1) % d;
            int r2 = (d - r1) % d;
            upd(total, right[i + 1][r2]);
        }
        have = (have + k[i] - '0') % d;
    }
    if (have == 0) upd(total, 1);

    cout << total << endl;

    return 0;
}


Measured memory_bytes: 4608
n=input()
lens=raw_input().split()
lens=[int(x) for x in lens]
lens.sort()
lens=lens[::-1]
i=0
needed=[]
while i<n-1:
    if lens[i] == lens[i+1]:
        needed.append(lens[i])
        i+=1
    i+=1
if len(needed)<2:print '0'
else: print needed[0]*needed[1]
        

Measured memory_bytes: 11832
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int i=0; i<n; i++)
typedef long long ll;
typedef pair<int,int> P;
const ll MOD = (int)1e9+7;
const ll INF = MOD*MOD;
const ll powll = 1LL<<1;

int main(){
  int n,m; cin >> n >> m;
  int dp[n+1] = {};
  int c[m]; rep(i,m) cin >> c[i];
  rep(i,n+1) dp[i] = MOD;
  dp[0] = 0;

  rep(i,n){
    rep(j,m){
      if(i+c[j] <= n) dp[i+c[j]] = min(dp[i+c[j]], dp[i]+1);
    }
  }
  cout << dp[n] << "\n";
}


Measured memory_bytes: 3312
// https://atcoder.jp/contests/

#include <bits/stdc++.h>
#define REP(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define REPR(i, n) for (int(i) = (n); (i) >= 0; (i)--)
#define FOR(i, m, n) for (int(i) = (m); (i) < (n); i++)
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int main()
{
  int N, w, sum = 0, t, minimum;
  vector<int> W;
  cin >> N;
  REP(i, N)
  {
    cin >> w;
    sum += w;
    W.push_back(sum);
  }

  minimum = sum;
  REP(i, N)
  {
    minimum = min(minimum, abs(sum - W[i] * 2));
  }
  cout << minimum << '\n';

  return 0;
}


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

bool alpha[30];

int main() {
    int N, max_count = 0, count;
    string S, s1, s2;
    cin >> N >> S;
    for (int i = 0; i < 30; i++) alpha[i] = false;
    for (int i = 1; i < S.length(); i++) {
        count = 0;
        s1 = S.substr(0, i);
        s2 = S.substr(i, S.length() - i);
        for (int j = 0; j < s1.length(); j++) alpha[s1[j] - 'a'] = true;
        for (int j = 0; j < s2.length(); j++) {
            if (alpha[s2[j] - 'a']) {
                count++;
                alpha[s2[j] - 'a'] = false;
            }
        }
        max_count = max(max_count, count);
    }
    cout << max_count << endl;
    return 0;
}

Measured memory_bytes: 256
# abc133_b.py
# 苦手な問題…ついに逃げられなくなってきたのでやる
N, D = map(int,input().split())
X = []
for i in range(N):
    X.append(list(map(int,input().split())))
cnt = 0
for i,p in enumerate(X):
    for j,q in enumerate(X):
        dist = 0
        if i!=j:
            for xi in range(D):
                dist += (p[xi]-q[xi])**2
            dist = dist**0.5
            if dist == int(dist):
#                print(p,q)
                cnt+=1
print(cnt//2)



Measured memory_bytes: 3060
import math
import sys

X = int(input())
X_soinsu = []
for i in range(1, int(math.sqrt(X))+1):
    if X % i == 0:
        X_soinsu.append(i)
        X_soinsu.append(X//i)

for abs_b in range(0, 10000):
    for b in [abs_b, -abs_b]:
        for soinsu in X_soinsu:
            a = b + soinsu
            if a**5 - b**5 == X:
                print(a, b)
                sys.exit(0)


Measured memory_bytes: 9064
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readIntList() = readLine()!!.split(" ").map(String::toInt)
fun readLongList() = readLine()!!.split(" ").map(String::toLong)
fun <T> Array<Array<T>>.print() {
    this.forEach {
        println(it.joinToString(" "))
    }
}

fun main() {
    val n = readInt()
    val a = readLongList().map { it.toBigInteger() }

    if (a.contains(0.toBigInteger())) {
        println(0)
        return
    }

    val res = a.reduce { acc, b ->
        val mul = acc * b
        if (mul > 1_000_000_000_000_000_000.toBigInteger()) {
            println(-1)
            return@main
        }
        mul
    }
    println(res)
}

Measured memory_bytes: 61988
#include<bits/stdc++.h>
using namespace std;
vector<long double> a;
long double x, ans = 0.0;
int n;
int main() {
    cout.precision(5);
    cin >> n;
    for (int i = 0; i<  n; i++) cin >> x, a.push_back(x), ans += (long double)1.0 / x;
    ans = (long double) 1.0 / ans;
    cout <<setprecision(20) << fixed << ans;
  return 0;
}

Measured memory_bytes: 256
import heapq
X, Y, Z, K = map(int, input().split())
A = sorted(map(int, input().split()), reverse=True)
B = sorted(map(int, input().split()), reverse=True)
C = sorted(map(int, input().split()), reverse=True)
que = [(-A[0] - B[0] - C[0], 0, 0, 0)]
used = set()
while K:
    s, i, j, k = heapq.heappop(que)
    if i + 1 < X and (i + 1, j, k) not in used:
        heapq.heappush(que, (-A[i + 1] - B[j] - C[k], i + 1, j, k))
        used.add((i + 1, j, k))
    if j + 1 < Y and (i, j + 1, k) not in used:
        heapq.heappush(que, (-A[i] - B[j + 1] - C[k], i, j + 1, k))
        used.add((i, j + 1, k))
    if k + 1 < Z and (i, j, k + 1) not in used:
        heapq.heappush(que, (-A[i] - B[j] - C[k + 1], i, j, k + 1))
        used.add((i, j, k + 1))
    s = -s
    print(s)
    K -= 1


Measured memory_bytes: 60248
N,P = map(int,input().split())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

a = factorization(P) 
su = 1
for j,k in a:
 # print(j,k,a)
  if k>=N:
    su *= j**(k//N)
  #  print(j,k,su)
print(su)
  

Measured memory_bytes: 3064
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define rrep(i,n) for(ll i##_len=(n) ,i=i##_len-1;i>=0;--i)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define fe(vec,lambda) std::for_each(vec.begin(), vec.end(), lambda );
#define printd(val) std::cout<< #val" = " <<val<<"\n";
#define printv(val) std::for_each(val.begin(),val.end(),[](auto x){cout<<x<<"\n";});
#define lim 1000000007ll
#include<bits/stdc++.h>
using ll = long long;
using pii = std::pair<ll,ll>;
using namespace std;
template<class T>T chmin(T& a,T b){if(a>b){a^=b;b^=a;a^=b;return 1;}return 0;}
template<class T>T chmax(T& b,T a){if(a>b){a^=b;b^=a;a^=b;return 1;}return 0;}
template <class T> T gcd(T a, T b){if (a < b) {a ^= b;b ^= a;a ^= b;} return b ? gcd(b, a % b) : a;}
template <class T> T lcm(T a, T b){return a * b / gcd(a, b);}
inline bool operator<(const pii &lhs,const pii &rhs){return(lhs.second<rhs.second);}
template<class T> vector<pair<T,T>> duplicator(const vector<T>& input){vector<pair<T,T>> out(input.size()-1);rep(i,input.size()-1){out[i].first =input[i  ];out[i].second=input[i+1];}return(out);}
vector<char> String_to_vector_char(const string& input){vector<char> out(input.size());rep(i,input.size()){out[i]=input[i];}return out;}


ll a,b,c;
vector<ll>v;
map<ll,ll>m;
string s[3];
void input(){
    cin>>s[0]>>s[1]>>s[2];
}
void src(){
    cout<< s[0][0] << s[1][0] << s[2][0];
}

int main(int argc,char* argv[]){
    ios::sync_with_stdio(false);
    //ifstream in( argv[1] ); cin.rdbuf(in.rdbuf());
    input();
    src();    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
using ll = long long int;

int main(){
    int n;
    cin >> n;
    vector<int> p(n);
    for(int i = 0; i < n; i++)cin >> p[i];

    vector<int> index(n+1);
    for(int i = 0; i < n; i++){
        index[p[i]] = i;
    }

    ll ans = 0;
    set<int> Lind;
    Lind.insert(index[n]);
    Lind.insert(-1); Lind.insert(n);
    for(int i = n-1; i > 0; i--){
        int nowind = index[i];
        set<int>::iterator it = Lind.upper_bound(nowind);
        int rmin = *it;
        --it;
        int lmax = *it;
        ++it;
        if (rmin != n){
            ++it;
            int rmax = *it;
            --it;
            ans += (ll)i * (rmax - rmin) * (nowind - lmax);
        }
        if (lmax != -1){
            --it;
            --it;
            int lmin = *it;
            ans += (ll)i * (lmax - lmin) * (rmin - nowind);
        }

        Lind.insert(nowind);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8260
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+5;
ll w[N];
vector<int>e[N];
int vis[N];
void dfs(int x,int fa)
{
    w[x]+=w[fa];
    for(auto v : e[x])
    {
        if(v==fa)continue;
        dfs(v,x);
    }
}
int main()
{
    int n,q,u,v;
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for(int i=1;i<=q;i++)
        scanf("%d%d",&u,&v),w[u]+=v;
    dfs(1,0);
    for(int i=1;i<=n;i++)
        printf("%lld ",w[i]);
    return 0;
}


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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

using ll = long long;
using ld = long double;
ll INF = LLONG_MAX;

using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;

namespace output {
	void pr(int x) { cout << x; }
	void pr(long x) { cout << x; }
	void pr(ll x) { cout << x; }
	void pr(unsigned x) { cout << x; }
	void pr(unsigned long x) { cout << x; }
	void pr(unsigned long long x) { cout << x; }
	void pr(float x) { cout << x; }
	void pr(double x) { cout << x; }
	void pr(ld x) { cout << x; }
	void pr(char x) { cout << x; }
	void pr(const char* x) { cout << x; }
	void pr(const string& x) { cout << x; }
	void pr(bool x) { pr(x ? "true" : "false"); }
	template<class T> void pr(const complex<T>& x) { cout << x; }
	
	template<class T1, class T2> void pr(const pair<T1,T2>& x);
	template<class T> void pr(const T& x);
	
	template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
		pr(t); pr(ts...); 
	}
	template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
		pr("{",x.f,", ",x.s,"}"); 
	}
	template<class T> void pr(const T& x) { 
		pr("{"); // const iterator needed for vector<bool>
		bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
		pr("}");
	}
	
	void print() { pr("\n"); } // print w/ spaces
	template<class T, class... Ts> void print(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(" "); print(ts...); 
	}
}

using namespace output;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll N, X, Y;
	cin >> N >> X >> Y;
	
	map<int, ll> count;
	FOR(i, 1, N+1) {
		FOR(j, i + 1, N+1) {
			ll dist = j - i;
			dist = min(dist, abs(i - X) + 1 + abs(j - Y));
			dist = min(dist, abs(i - Y) + 1 + abs(j - X));
			count[dist]++;
		}
	}
	FOR(k, 1, N) print(count[k]);
	
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#include<cmath>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;
const ll MOD = 1000000007;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(ll i=num, i##_len=(n); i<i##_len; ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};
#define print(x) cout << (x) << endl;
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
 
template<typename T>
T gcd(T a,T b){return b?gcd(b,a%b):a;}

const int INF = 1e9;
const ll LLINF = 1e16;
 
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}
 
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
 
template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}
 
template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}
 
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
 
template<typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

// 割り算の切り上げ処理
template<typename T>
T round_up(T a, T b) {
  return (a + b - 1) / b;
}

vector<pair<long long, long long> > prime_factorize(long long n) { //素因数分解、pairのfirstに底、secondに底の何乗
   vector<pair<long long, long long> > res;
   for (long long p = 2; p * p <= n; ++p) {
       if (n % p != 0) continue;
       int num = 0;
       while (n % p == 0) { ++num; n /= p; }
       res.push_back(make_pair(p, num));
   }
   if (n != 1) res.push_back(make_pair(n, 1));
   return res;
}

using pint = pair<int, int>;
using pll = pair<ll, ll>;

ll dp[10100][10100];
int main(void)
{
    cout.tie(0);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    ll h,n;
    cin >> h >> n;
    vector<ll> a(n);
    vector<ll> b(n);
    rep(i,n){
      cin >> a[i] >> b[i];
    }
    rep(i,10100){
      rep(j,10100){
        dp[i][j] = LLINF;
      }
    }
    dp[0][0] = 0;
    rep(i, n){
      rep(j, h+1){
        if(j < a[i]) {
          dp[i + 1][j] = min(dp[i][j], dp[i + 1][0] + b[i]);
        } else {
          dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - a[i]] + b[i]);
        }
      }
    }
    
    print(dp[n][h]);
}


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

int main(){
  string sd, t, s;
  cin >> sd >> t;
  int i, j, k;
  for(i = sd.size()-t.size() ; i >= 0; i--){
    s = sd;
    for(j = 0 ; j < t.size() ; j++){
      if(s[i+j] == '?'){
        s[i + j] = t[j];
      } else if(s[i + j] != t[j]) {
        break;
      }
      if(j == t.size()-1){
        for(k = 0; k < sd.size(); k++){
          if(s[k] == '?'){
            s[k] = 'a';
          }
        }
        cout << s << endl;
        return 0;
      }
    }
  }
  cout << "UNRESTORABLE" << endl;
  return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include<algorithm> 
#include <iomanip>
#include <math.h>

#define db double
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define maxn 5005
#define mod 998244353
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vll vector<ll>
#define vpi vector<pii>
#define vpll vector<pll>
#define vv(z,a,b) vector<vector<int>>z(a,vector<int>(b))
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(c) begin(c),end(c)
using namespace std;


int main(){
   int n,m;cin>>n>>m;
   vv(s,m,11);
   vi k(m);
   vi p(m);
   int sum=0;
   rep(i,m){
       cin>>k.at(i);
        rep(j,k.at(i)){
            cin>>s.at(i).at(j);
        }
   }
    rep(i,m)cin>>p.at(i);
for(int bits=0;bits<(1<<n);bits++){
    int ans=0;
    if(bits==0){
        rep(i,m){
            if(p.at(i)!=0)break;
            if(i==m-1)sum++;
        }
        continue;
    }
    rep(i,m){
        int flag=0;
        rep(j,k.at(i)){
            if(bits&(1<<(s.at(i).at(j)-1)))flag++;
        }
        if((flag%2)==p.at(i))ans++;
        else {
            ans=0;
            break;
        }
    }
    if(ans==m)sum++;
}
cout<<sum<<endl;
}

Measured memory_bytes: 256
from collections import Counter

N = int(input())
S = Counter(input() for _ in range(N))
M = int(input())
T = Counter(input() for _ in range(M))

ma = 0
for s in S.keys():
    if s in T:
        ma = max(ma, S[s] - T[s])
    else:
        ma = max(ma, S[s])

print(ma)



Measured memory_bytes: 3316