akhauriyash/Code-Regression huggingface dataset:
//Name: Get Many Persimmon Trees
//Level: 2
//Category: 動的計画法,DP,累積和
//Note:

/*
 * 二次元累積和で木の数を覚えておき、建物の左上座標を全通り試す。
 *
 * オーダーは O(WH)。
 */
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool solve() {
    int N;
    if(!(cin >> N)) return false;
    if(!N) return false;

    int W, H;
    cin >> W >> H;

    vector<vector<int>> field(H, vector<int>(W, 0));
    for(int i = 0; i < N; ++i) {
        int x, y;
        cin >> x >> y;
        field[y-1][x-1]++;
    }

    for(int r = 0; r < H; ++r) {
        for(int c = 0; c < W; ++c) {
            if(r > 0) field[r][c] += field[r-1][c];
            if(c > 0) field[r][c] += field[r][c-1];
            if(r > 0 && c > 0) field[r][c] -= field[r-1][c-1];
        }
    }

    int S, T;
    cin >> S >> T;
    int ans = 0;
    for(int r = 0; r <= H-T; ++r) {
        for(int c = 0; c <= W-S; ++c) {
            int sum = field[r+T-1][c+S-1];
            if(r > 0) sum -= field[r-1][c+S-1];
            if(c > 0) sum -= field[r+T-1][c-1];
            if(r > 0 && c > 0) sum += field[r-1][c-1];
            ans = max(ans, sum);
        }
    }
    cout << ans << endl;
    return true;
}

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

    while(solve()) ;
    return 0;
}

Measured memory_bytes: 1264
def F(a, b):
    count = 0
    c = max(a, b)
    while c >= 10:
        c = c / 10
        count += 1
    return count+1
 
N = int(input())
minimum = 15
for num in range(1,int(N**0.5)+1):
    if N % num == 0:
        minimum = min(minimum, F(num, N/num))
print(minimum)

Measured memory_bytes: 3064
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n = int(input())
  Ps = list(map(int, input().strip().split()))
  print(sum([Ps[i] < Ps[i+1] < Ps[i+2] or Ps[i] > Ps[i+1] > Ps[i+2] for i in range(n-2)]))

if __name__=='__main__':
  main()



Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000001;
constexpr ll INF= 1e18;
constexpr ll MOD = 998244353;
const double PI = 3.1415926535897;
typedef pair<int,int> P;

int main() {
    int K,N;
    cin >> K >> N;
    vector<int> vec(N);
    for(int i = 0;i < N;i++) {
        cin >> vec.at(i);
    }
    int ret = K;
    for(int i = 0;i < N - 1;i++) {
        ret = min(ret,K - (vec.at(i + 1) - vec.at(i)));
    }
    ret = min(ret,K - (vec.at(0) + K - vec.at(N - 1)));
    cout << ret << endl;
}

Measured memory_bytes: 1152
#include<iostream>
#include<iomanip>
#include<algorithm>

using namespace std;

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

int main(){
    string a, b, c;
    cin >> a >> b >> c;
  	int A, B, C; 
  	A = a.size(); B = b.size();
  	if(a.at(A-1) == b.at(0) && b.at(B-1) == c.at(0)){
    	cout << "YES" << endl;
    }
  	else cout << "NO" << endl;
  return 0;
}



Measured memory_bytes: 256
n, m = map(int, input().split())
As = [int(input()) for i in range(m)]


dp = [0] * (n+1)
mod = 10**9 + 7
# 配るdp ではなくもらうdpで書くようにしてみる
is_safe = [True] * (n+1)
for i in range(m):
    is_safe[As[i]] = False



for i in range(n+1):
    if i == 0:
        dp[i] = 1
    
    elif not is_safe[i]:
        dp[i] = 0
    elif i == 1:
        dp[i] = dp[i-1]
    else:
        dp[i] = (dp[i-1] % mod + dp[i-2] % mod) % mod


print(dp[n])


Measured memory_bytes: 8616
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

int n;
int u[200000], v[200000];

signed main() {
	int i;
	
	cin >> n;
	rep(i, n - 1) { cin >> u[i] >> v[i]; u[i]--; v[i]--; }
	
	int tyoten = 0;
	for (i = 1; i <= n; i++) {
		tyoten += i * (n + 1 - i);
	}
	
	int hen = 0;
	rep(i, n - 1) {
		if (u[i] > v[i]) swap(u[i], v[i]);
		hen += (u[i] + 1) * (n - v[i]);
	}
	
	cout << tyoten - hen << endl;
	return 0;
}

Measured memory_bytes: 6756
a, b, c, d = gets.chomp.split.map(&:to_i)

c_num = (b / c) - (a / c)
c_num += 1 if a % c == 0
d_num = (b / d) - (a / d)
d_num += 1 if a % d == 0

# 最小公倍数
e = [c, d].max
f = [c, d].min

p = e * f

while true do
  # q = e / f
  r = e % f
  if r == 0
    p = f
    break
  end

  e = f
  f = r
end

g = c / p * d

g_num = (b / g) - (a/ g)
g_num += 1 if a % g == 0
puts b - a + 1 - (c_num + d_num - g_num)

Measured memory_bytes: 1788
from collections import deque

N = int(input())
S = deque(list(input()))

def main():
    ans = 0
    curr = 0
    while S:
        s = S.popleft()
        curr += 1 if s == 'I' else -1
        ans = max(ans, curr)
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
 
s = rr()
if s.isupper():
    print('A')
else:
    print('a')

Measured memory_bytes: 64704
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, S, A):
    M = 998244353
    ans = 0

    dp = [0] * (S+1)
    for a in A:
        dp[0] += 1
        ndp = [0] * (S+1)
        for j in range(S+1):
            ndp[j] += dp[j]
            ndp[j] %= M
            if j+a <= S:
                ndp[j+a] += dp[j]
                ndp[j+a] %= M
        dp = ndp
        ans += dp[S]
        ans %= M

    return ans


def main():
    N, S = read_int_n()
    A = read_int_n()
    print(slv(N, S, A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 62440
/***************************************** START OF TEMPLATE *********************************************/

#include<bits/stdc++.h>

using namespace std;

#define  SPEED          ios:: sync_with_stdio(0);cin.tie(0);cout.tie(0);cout<<fixed;cout<<setprecision(10);
#define  randomINIT     mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define  foo(i,a,n)     for(ll i = (a); i <= n; i++)
#define  frr(i,a,n)     for(ll i = (a); i >= n; i--)
#define  fo(i,n)        for(ll i = 0; i < n; i++)
#define  all(x)         (x).begin(),(x).end()
#define  mset(x,val)    memset(x,val,sizeof(x))
#define  newl           cout<<"\n"
#define  f              first
#define  s              second
#define  pb             push_back
#define  INPa(a,n)      foo(i,1,n) cin>>a[i];
#define  deb2d(a,n,m)   foo(i,1,n){foo(j,1,m){cout<<a[i][j]<<" ";}newl;}    
#define  deb1d(a,n)     foo(i,1,n)cout<<a[i]<<" ";newl;
#define  debv(a)        for(auto it: a)cout<<it<<" ";newl;
#define  deb1(a)        cout<<a<<" ";newl;
#define  deb2(a,b)      cout<<a<<" "<<b<<" ";newl;
#define  deb3(a,b,c)    cout<<a<<" "<<b<<" "<<c<<" ";newl;
#define  deb4(a,b,c,d)  cout<<a<<" "<<b<<" "<<c<<" "<<d;newl;
#define  ll             long long
#define  ld             long double
#define  pll            pair<ll,ll>
#define  vll            vector<ll>
#define  vpll           vector<pll>

const ll   MOD   =  1e+9+7;
const ll   INF   =  LLONG_MAX;
const int  INFi  =  INT_MAX;
const ll   N     =  2e+5+8;

vll adj[N]; ll vis[N];
ll dx4[]={0,1,0,-1}, dy4[]={1,0,-1,0};

ll test_cases = 1; randomINIT;

/*********************************************************************************************************/
/***************************************** VARIABLE DECLARATIONS *****************************************/
ll n, pre[N], suf[N], res = 0;
string s;

/***************************************** FUNCTION IMPLEMENTATIONS **************************************/
ll solve(char f, char m, char t){
    //clean up
    ll res = 0;
    foo(i,0,n+1) pre[i] = suf[i] = 0;

    //pre process
    foo(i,1,n){
        if(s[i] == f) pre[i] = pre[i-1] + 1;
        else pre[i] = pre[i-1];
    }
    frr(i,n,1){
        if(s[i] == t) suf[i] = suf[i+1] + 1;
        else suf[i] = suf[i+1];
    }

    //solve
    foo(i,1,n){
        if(s[i] == m){
            res += pre[i-1] * suf[i+1];
        }
    }
    foo(i,1,n){
        if(s[i] == m){
            for(ll L = i-1, R = i+1; L>=1 && R<=n; L--, R++){
                if(s[L] == f && s[R] == t) res -= 1;
            }
        }
    }

    return res;
}


/***************************************** START OF MAIN FUNCTION ****************************************/
void MAIN(ll tc){
    cin>>n>>s; s = "#"+s+"#";
    res += solve('R','G','B');
    res += solve('R','B','G');
    res += solve('G','R','B');
    res += solve('G','B','R');
    res += solve('B','G','R');
    res += solve('B','R','G');
    cout<<res;
}

int main(){
    SPEED;

    //cin>>test_cases;
    foo(i,1,test_cases){
        MAIN(i);
    }
}

Measured memory_bytes: 8392
#include <bits/stdc++.h>
#define pan(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define vi vector<int>
#define pb push_back
#define INF 1e9+7
#define inf 100001
#define PI 3.141592653
using namespace std; 

int main(){
    int n;
    cin>>n;
    vi v,p;
    pan(i,n){int x;
        cin>>x;
        if(i%2==0) v.pb(x);
        else p.pb(x);
    }
    int o=0,o1=-1,e=0,e1=-1,x[inf],y[inf];
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    for(int i=0;i<v.size();i++) x[v[i]]++;
    int ce=*max_element(x,x+inf);
    e=distance(x,max_element(x,x+inf));
    x[e]=0;
    int ce1=*max_element(x,x+inf);
    e1=distance(x,max_element(x,x+inf));
    pan(i,p.size()) y[p[i]]++;
    int co=*max_element(y,y+inf);
    o=distance(y,max_element(y,y+inf));
    y[o]=0;
    int co1=*max_element(y,y+inf);
    o1=distance(y,max_element(y,y+inf));
    int ans=0;
    if(o!=e) ans=n-co-ce;
    else{
        ans=min(n-co-ce1,n-co1-ce);
    }
    cout<<ans;
} 

Measured memory_bytes: 1660
#include<iostream>
using namespace std;
const int inf=1e9,sz=100;
int g[sz][sz],gg[sz][sz];

main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)g[i][j]=inf;
        g[i][i]=0;
    }
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        u--;v--;
        gg[u][v]=g[u][v]=min(g[u][v],w);
        gg[v][u]=g[v][u]=min(g[v][u],w);   
    }
    for(int k=0;k<n;k++)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
            }
        }
    }

    int ans=m;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(g[i][j]!=inf&&g[i][j]==gg[i][j])ans--;
        }
    }
    cout<<ans;
    return 0;
}

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

int main(){

  string S, T;
  
  cin >> S >> T;
  
  if(S.size() != T.size() - 1){
    cout << "No" << endl;
    return 0;
  }
  
  for(int i = 0; i < S.size(); i++){
    if(S[i] != T[i]) { 
      cout << "No" << endl;
      return 0;}
  }
  
  cout << "Yes" << endl;
}
  


Measured memory_bytes: 3628
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var a, b, k string
	fmt.Scan(&a, &b, &k)
	A, _ := strconv.ParseInt(a, 10, 64)
	B, _ := strconv.ParseInt(b, 10, 64)
	K, _ := strconv.ParseInt(k, 10, 64)

	if K >= A+B {
		fmt.Println(0, 0)
	} else if K >= A {
		fmt.Println(0, B-(K-A))
	} else {
		fmt.Println(A-K, B)
	}

}


Measured memory_bytes: 512
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

n = ni()
s = list(ns())
k = ni()
a = s[k - 1]
for i in range(len(s)):
    if s[i] != a:
        s[i] = '*'
print(''.join(s))


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

using namespace std;

int main()
{
    int n,m;
    cin >> n >> m;
    vector<bool> v(n+1,0);
    vector<int> cnt(n+1,0);
    int ok=0,wa=0;
    for(int i=0;i<m;i++)
    {
        int t;
        string s;
        cin >> t >> s;
        if(s=="AC")
        {
            if(v[t]==0) ok++;
            v[t]=1;
        }
        else
        {
            if(v[t]==0) cnt[t]++;
        }
    }
    for(int i=1;i<=n;i++) if(v[i]==1) wa+=cnt[i];
    cout << ok << " " << wa << endl;
    return 0;
}


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

void my_call(int n) {
  int i = 1;
  do {
    int x = i;

    if (x % 3 == 0) {
      cout << " " << i;
      continue;
    }

    do {
      if (x % 10 == 3) {
        cout << " " << i;
        break;
      }
    } while (x /= 10);
  } while (++i <= n);
  cout << endl;
}

int main() {
  int n;
  cin >> n;
  my_call(n);
}



Measured memory_bytes: 3080
n,m = map(int,input().split())
stds = [tuple(map(int,input().split())) for _ in range(n)]
points = [tuple(map(int,input().split())) for _ in range(m)]

def d(s,p):
  return abs(s[0]-p[0]) + abs(s[1] - p[1])

for std in stds:
  ans = (-1, float('inf'))
  for i, pnt in enumerate(points):
    dst = d(std,pnt)
    if dst < ans[1]:
      ans = (i, dst)
  print(ans[0]+1)



Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repo(i, n) for(int i=1; i<=n; i++)
#define ssort(a) sort(a.begin(), a.end(), greater<ll>())
#define INF 1001001001
#define INFll 100100100100100
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;

using namespace std;
using ull = unsigned long long;
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

bool added[1005][1005][1005];

struct element{
  ll abc;
  int ei;
  int ej;
  int ek;
};

struct Compareabc {
    bool operator()(element const& p1, element const& p2)
    {
        // return "true" if "p1" is ordered
        // before "p2", for example:
        return p1.abc < p2.abc;
    }
};

int main(){
  int x, y, z, k;
  cin >> x >> y >> z >> k;
  vector<ll> a(x);
  vector<ll> b(y);
  vector<ll> c(z);
  rep(i, x){
    cin >> a[i];
  }
  rep(i, y){
    cin >> b[i];
  }
  rep(i, z){
    cin >> c[i];
  }
  ssort(a);ssort(b);ssort(c);
  priority_queue<element, vector<element>, Compareabc> PQ;
  element e0={a[0]+b[0]+c[0], 0, 0, 0};
  PQ.push(e0);
  rep(qi, k){
    element p=PQ.top(); PQ.pop();
    cout << p.abc << endl;
    if(p.ei+1<x && !added[p.ei+1][p.ej][p.ek]){
      element e1={a[p.ei+1]+b[p.ej]+c[p.ek], p.ei+1, p.ej, p.ek};
      PQ.push(e1);
      added[p.ei+1][p.ej][p.ek]=true;
    }
    if(p.ej+1<y && !added[p.ei][p.ej+1][p.ek]){
      element e2={a[p.ei]+b[p.ej+1]+c[p.ek], p.ei, p.ej+1, p.ek};
      PQ.push(e2);
      added[p.ei][p.ej+1][p.ek]=true;
    }
    if(p.ek+1<z && !added[p.ei][p.ej][p.ek+1]){
      element e3={a[p.ei]+b[p.ej]+c[p.ek+1], p.ei, p.ej, p.ek+1};
      PQ.push(e3);
      added[p.ei][p.ej][p.ek+1]=true;
    }
  }

  return 0;
}


Measured memory_bytes: 8644
<?php
$n=trim(fgets(STDIN));
$i=0;
while($i<$n){
  list($s[],$t[])=explode(" ",trim(fgets(STDIN)));
  ++$i;
}
$x=trim(fgets(STDIN));
$c=array_search($x,$s);
$ans=0;
$i=$c+1;
while($i<$n){
  $ans+=$t[$i];
  ++$i;
}
echo $ans;

Measured memory_bytes: 4856
#include <stdio.h>
int main(void){
  long int N, K, a, b;
    scanf("%ld", &N); scanf("%ld", &K);
    a = N % K;
    b = a - K;
  	if(b < 0) b *= -1;
    if (a < b) printf("%ld\n", a);
    else printf("%ld\n", b);
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char word[200010];
long long ans,tmp;
int main()
{
	scanf("%s",word);
	for(int i=0;i<strlen(word);i++)
	{
		if(word[i]=='W')
		{
			ans+=i-tmp;
			tmp++;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 384
program sample
implicit none
character(len=13) :: x,y
integer(8) :: i,j
real(8),allocatable :: a(:),b(:)

read(*,*) x

do i=13,6,-1
x(i:i)=x(i-1:i-1)
end do

x(5:5)=' '

write(*,'(a)') trim(x)
!write(*,*) 'ABCD EFGHIJKL'

end program sample

Measured memory_bytes: 2820
N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())
ls = [A,B,C,D,E]
X = min((A,B,C,D,E))
s=N//X
if N%X==0:
  s-=1
print(s+5)

Measured memory_bytes: 3064
#include <stdio.h>

const int MAX = 200000;

int main( void ) {
	int i,n,min;
	int max = -1000000000;
	int rt[MAX];

	scanf( "%d", &n );
	for( i = 0; i < n; i++ ) scanf( "%d", &rt[i] );

	min = rt[0];
	for( i = 1; i < n; i++ ) {
		if ( max < (rt[i] - min) ) max = rt[i] - min;
		if ( min > rt[i] ) min = rt[i];
	}

	printf( "%d\n", max );

	return 0;
}


Measured memory_bytes: 2588
#include <iostream>
#include <iomanip>
#include <random>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <sstream>
#include <bitset>
#include <cassert>
#include <fstream>
#include <queue>

#define len(X) ((int)(X).size())

#ifdef __LOCAL
	#define DBG(X) cout << #X << "=" << (X) << '\n';
#else
	#define DBG(X)
#endif

using std::cin;
using std::cout;
using std::vector;
using std::string;
using std::pair;
using std::swap;
using std::sort;
using std::lower_bound;
using std::unique;
using std::abs;

using int64 = long long int;
using pii   = pair<int, int>;
using pii64 = pair<int64, int64>;

const int NIL = -1;
const int INF = (int)2e9;
const int64 INF64 = (int64)2e18;

void init_IO() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const vector<T>& vec) {
	os << '[';
	int fst = 1;

	for(auto& elem: vec) {
		if(fst == 0) {
			os << ' ';
		}

		os << elem;
		fst = 0;
	}

	os << ']';
	return os;
}

void solve() {
	int n, m;
	cin >> n >> m;
	++n;

	vector<int> a = {0};

	for(int i = 1; i < n; ++i) {
		int value;
		cin >> value;

		a.push_back(value % m);
	}

	for(int i = 1; i < n; ++i) {
		a[i] += a[i - 1];

		if(a[i] >= m)
			a[i] -= m;
	}

	sort(a.begin(), a.end());
	int64 answ = 0;

	for(int i = 0; i < n;) {
		int j = i;

		while(j + 1 < n && a[j + 1] == a[i]) {
			++j;
		}

		int64 sz = j - i + 1;
		answ += (sz * (sz - 1)) / 2;
		i = j + 1;
	}

	cout << answ << '\n';
}

int main() {
	init_IO();
	solve();

	return 0;
}


Measured memory_bytes: 892
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
#define MOD 1000000007LL
#define PI 3.141592653589793
#define endl "\n"

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll H, W;
  cin >> H >> W;
  vector<string> S(H);
  queue<P> que;
  vvll num(H, vll(W, INF));
  for(int i = 0; i < H; i++){
    cin >> S.at(i);
    for(int j = 0; j < W; j++){
      if(S.at(i).at(j) == '#'){
        que.push(P(i, j));
        num.at(i).at(j) = 0;
      }
    }
  }
  vi dx = {1, -1, 0, 0};
  vi dy = {0, 0, 1, -1};
  while(!que.empty()){
    int yy = que.front().first;
    int xx = que.front().second;
    que.pop();
    int nn = num.at(yy).at(xx);
    for(int i = 0; i < 4; i++){
      int ny = yy + dy.at(i);
      int nx = xx + dx.at(i);
      if(ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
      if(num.at(ny).at(nx) > nn + 1){
        num.at(ny).at(nx) = nn + 1;
        que.push(P(ny, nx));
      }
    }
  }
  ll ans = 0LL;
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      chmax(ans, num.at(i).at(j));
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 17424
n = int(input())
combiList = {}

for _ in range(n):
    act_string = list(input())
    act_string.sort()
    act_string = "".join(act_string)
    
    if combiList.get(act_string) is None:
        combiList[act_string] = 1
    else:
        combiList[act_string] += 1
sum_cnt = 0
for cnt in combiList.values():
    sum_cnt += cnt * (cnt - 1) / 2

print(int(sum_cnt))

Measured memory_bytes: 17932
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <fstream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
using namespace std;
#define     loop(n,i,a)     for(int i=a;i<n;i++)
#define     loopR(n,i,a)    for(int i=n-1;i>=a;i--)
#define     all(arr,n)      arr,arr+n
#define     allv(v)         (v).begin(),(v).end()
#define     rallv(v)        (v).rbegin(),(v).rend()
#define     m_p             make_pair
#define     ll              long long
#define     pii             pair<ll,ll>
#define     vi              vector<int>
#define     vll             vector<ll>
#define		vii 			vector<pair<ll,ll>>
#define     sz(x)           (int)x.size()
#define     pb              push_back
#define     endl            "\n"
#define     Endl            "\n"
#define     f               first
#define     s               second
#define     mem(dp,n)       memset(dp,n,sizeof dp)
#define     test(i)        cout<<i<<endl
int dx[] = { 1 , 0 ,-1 , 0 ,-1 ,-1 , 1 , 1 };
int dy[] = { 0 , 1 , 0 ,-1 ,-1 , 1 ,-1 , 1 };
void fast(){
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
        vector<string> __attribute__ ((unused)) args,
        __attribute__ ((unused)) int idx,
        __attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
const ll mxN=3e2+10,oo=0x3f3f3f3f,mod=998244353;
const double PI = 3.14159265358979323846;

void solve(){
    int n,k;
    cin>>n>>k;
    ll arr[n+1];
    loop(n+1,i,1)
        cin>>arr[i];
    loop(n+1,i,k+1){
        if(arr[i]>arr[i-k])
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }

}
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    fast();
    solve();
}

Measured memory_bytes: 5180
#include <iostream>
#include <vector>
#include <map>
#include <deque>
#include <queue>
#include <algorithm>

using namespace std;

template <class T>
bool chmin(T &x, T y)
{
    return x>y ? (x=y, true) : false;
}
template <class T>
bool chmax(T &x, T y)
{
    return x<y ? (x=y, true) : false;
}

main()
{
    int X,Y; cin>>X>>Y;
    int A,B,C; cin>>A>>B>>C;
    vector<int> p(A),q(B),r(C);
    for(auto &e: p) cin>>e;
    for(auto &e: q) cin>>e;
    for(auto &e: r) cin>>e;
    sort(rbegin(p), rend(p));
    sort(rbegin(q), rend(q));
    sort(rbegin(r), rend(r));
    p.erase(p.begin()+X, p.end());
    q.erase(q.begin()+Y, q.end());
    vector<int> pq(X+Y);
    copy(begin(p),end(p),begin(pq));
    copy(begin(q),end(q),begin(pq)+X);
    sort(begin(pq),end(pq));
    long long now=0;
    for(auto e: pq) now+=e;
    long long ans=0;
    for(int i=0;i<=C and i<X+Y; ++i)
    {
        chmax(ans, now);
        if(i<X+Y) now-=pq[i];
        if(i<C) now+=r[i];
    }
    cout << ans << "\n";
}

Measured memory_bytes: 2176
#include <iostream>
#include <cmath>
#include <iomanip>
#define pi 3.14159265359
using namespace std;

double calc_D(double a, double b){
  return sqrt(a * a + b * b);
}

int main() {
  double a;
  double b;
  double c;
  double d;
  cin >> a >> b >> c >> d;
  double c_x;
  double c_y;
  double d_x;
  double d_y;
  
  double hour_pi = 2 * pi / 12;
  double minute_pi = 2 * pi / 60;
  
  c_x = a * sin(hour_pi * c + hour_pi * d / 60);
  c_y = a * cos(hour_pi * c + hour_pi * d / 60);
  d_x = b * sin(minute_pi * d);
  d_y = b * cos(minute_pi * d); 
  
  double distance = calc_D(c_x - d_x, c_y - d_y);
  
  cout << setprecision(12) << distance << endl;
  
}

Measured memory_bytes: 4060
#include<iostream>
#include<queue>
#include<algorithm>
#include<numeric>
#include<string>
#include<map>
#include<bitset>

using namespace std;
using int_greater_PQ = priority_queue<int,vector<int>,greater<int>>;


int main() 
{
    int N;
    cin>>N;
    
    auto n=static_cast<double>(N);
    double a;

    if(N%2==0)
    {
        a=(n/2)/n;
    }
    else
    {
        a=((n+1)/2)/n;
    }
    


    cout<<a<<endl;
    return 0;
}



Measured memory_bytes: 3744
#include <algorithm> // for sorting
#include <iostream>
#define int long long
using namespace std;
#define mod 1000000007

// Required function
int maxProductSubarrayOfSizeK(int A[], int n, int k)
{
    // sorting given input array
    sort(A, A + n);

    // variable to store final product of all element
    // of sub-sequence of size k
    int product = 1;

    // CASE I
    // If max element is 0 and
    // k is odd then max product will be 0
    if (A[n - 1] == 0 && (k & 1))
        return 0;

    // CASE II
    // If all elements are negative and
    // k is odd then max product will be
    // product of rightmost-subarray of size k
    if (A[n - 1] <= 0 && (k & 1))
    {
        for (int i = n - 1; i >= n - k; i--)
            product = (((product + mod) % mod) * ((A[i] + mod) % mod)) % mod;
        return product;
    }

    // else
    // i is current left pointer index
    int i = 0;

    // j is current right pointer index
    int j = n - 1;

    // CASE III
    // if k is odd and rightmost element in
    // sorted array is positive then it
    // must come in subsequence
    // Multiplying A[j] with product and
    // correspondingly changing j
    if (k & 1)
    {
        product = (product * ((A[j] + mod) % mod)) % mod;
        j--;
        k--;
    }

    // CASE IV
    // Now k is even
    // Now we deal with pairs
    // Each time a pair is multiplied to product
    // ie.. two elements are added to subsequence each time
    // Effectively k becomes half
    // Hence, k >>= 1 means k /= 2
    k >>= 1;
    //cout << product << i << " " << j << "\n";
    // Now finding k corresponding pairs
    // to get maximum possible value of product
    for (int itr = 0; itr < k; itr++)
    {

        // product from left pointers
        int left_product = (A[i] * A[i + 1]);

        // product from right pointers
        int right_product = (A[j] * A[j - 1]);
        // Taking the max product from two choices
        // Correspondingly changing the pointer's position
        if (left_product > right_product)
        {
            product = (((product + mod) % mod) * ((left_product + mod) % mod)) % mod;
            i += 2;
        }
        else
        {
            product = (((product + mod) % mod) * ((right_product + mod) % mod)) % mod;
            j -= 2;
        }
    }

    // Finally return product
    return product % mod;
}

// Driver Code to test above function
int32_t main()
{
    int n, k;
    cin >> n >> k;
    int arr[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    cout << maxProductSubarrayOfSizeK(arr, n, k);

    return 0;
}

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

string forwardTrans(char c){
	if(c == ' ') return "101";
	else if(c == '\'') return "000000";
	else if(c == ',') return "000011";
	else if(c == '-') return "10010001";
	else if(c == '.') return "010001";
	else if(c == '?') return "000001";
	else if(c == 'A') return "100101";
	else if(c == 'B') return "10011010";
	else if(c == 'C') return "0101";
	else if(c == 'D') return "0001";
	else if(c == 'E') return "110";
	else if(c == 'F') return "01001";
	else if(c == 'G') return "10011011";
	else if(c == 'H') return "010000";
	else if(c == 'I') return "0111";
	else if(c == 'J') return "10011000";
	else if(c == 'K') return "0110";
	else if(c == 'L') return "00100";
	else if(c == 'M') return "10011001";
	else if(c == 'N') return "10011110";
	else if(c == 'O') return "00101";
	else if(c == 'P') return "111";
	else if(c == 'Q') return "10011111";
	else if(c == 'R') return "1000";
	else if(c == 'S') return "00110";
	else if(c == 'T') return "00111";
	else if(c == 'U') return "10011100";
	else if(c == 'V') return "10011101";
	else if(c == 'W') return "000010";
	else if(c == 'X') return "10010010";
	else if(c == 'Y') return "10010011";
	else if(c == 'Z') return "10010000";
}

char backwardTrans(string s){
	if(s == "00000") return 'A';
	else if(s == "00001") return 'B';
	else if(s == "00010") return 'C';
	else if(s == "00011") return 'D';
	else if(s == "00100") return 'E';
	else if(s == "00101") return 'F';
	else if(s == "00110") return 'G';
	else if(s == "00111") return 'H';
	else if(s == "01000") return 'I';
	else if(s == "01001") return 'J';
	else if(s == "01010") return 'K';
	else if(s == "01011") return 'L';
	else if(s == "01100") return 'M';
	else if(s == "01101") return 'N';
	else if(s == "01110") return 'O';
	else if(s == "01111") return 'P';
	else if(s == "10000") return 'Q';
	else if(s == "10001") return 'R';
	else if(s == "10010") return 'S';
	else if(s == "10011") return 'T';
	else if(s == "10100") return 'U';
	else if(s == "10101") return 'V';
	else if(s == "10110") return 'W';
	else if(s == "10111") return 'X';
	else if(s == "11000") return 'Y';
	else if(s == "11001") return 'Z';
	else if(s == "11010") return ' ';
	else if(s == "11011") return '.';
	else if(s == "11100") return ',';
	else if(s == "11101") return '-';
	else if(s == "11110") return '\'';
	else if(s == "11111") return '?';
}

int main(){
	string s, tmp;
	int rest;
	while (getline(cin, s)) {
		tmp = "";
		for (int i = 0; i < s.size(); i++) {
			tmp += forwardTrans(s[i]);
		}
		rest = tmp.size() % 5;
		if (rest != 0) {
			for (int i = 0; i < (5-rest); i++) {
				tmp += "0";
			}
		}
		for (int i = 0; i < tmp.size(); i += 5) {
			cout << backwardTrans(tmp.substr(i, 5));
		}
		cout << endl;
	}
	return 0;
}

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

public class Main {
    public static void main(String[] args){
    	
    	try {
    		InputStreamReader isr = new InputStreamReader(System.in);
    		BufferedReader br = new BufferedReader(isr);
    		String buf = br.readLine();
    		StringTokenizer st=new StringTokenizer(buf," ");
    		int W = Integer.parseInt(st.nextToken());	//高さ(H)…height
    		int H = Integer.parseInt(st.nextToken());	//幅(W)…wide
    		int x = Integer.parseInt(st.nextToken());	//x軸は横 幅に関係
    		int y = Integer.parseInt(st.nextToken());	//y軸は縦 高さに関係
    		int r = Integer.parseInt(st.nextToken());	//半径

    		if(-100 <=x && x<=100 && -100 <=y && y<=100 && 0<W && W <=100 && 0<H && H <=100 && 0<r && r <=100){

    			if( (x-r) >= 0 && (x+r) <= W && (y-r) >=0 && (y+r) <= H ){

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

    	} catch(IOException e) {
		    System.err.println(e);
		}

    }
}

Measured memory_bytes: 17056
from sys import stdin
from itertools import permutations,product

while(True):
    lis = stdin.readline().split()
    if lis == ["0","0","0","0"]: break
    for [a,b,c,d],[e,f,g],h in product(permutations(lis),product(["+","*","-"],repeat=3),range(7)):
        st = "("*(h>>2)+a+e+\
                "("*(1 if h in [2,3] else 0)+b+\
                ")"*(1 if h in [4,5] else 0)+f+\
                "("*(1 if h in [1,5] else 0)+c+\
                ")"*(1 if h in [2,6] else 0) +g+d+\
                ")"*(h&5>>2)
        if eval(st) == 10: print(st); break
    else:
        print(0)



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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

const string YES = "Yes";
const string NO = "No";
const ll mod = 1e9+7;


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

    int k,x; cin >> k >> x;
    int mn = max(-1000000, x-k+1);
    int mx = min(1000000, x+k-1);
    for(int i=mn;i<=mx;i++){
        cout << i << " ";

    }

    return 0;
    
}



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

int main(){
    int i, n, a = 9999;
    string s;
    cin >> s;
    for(i=0; i<s.size()-2; i++){
        n = (int)100*(s[i]-'0') + 10*(s[i+1]-'0') + (s[i+2]-'0');
        a = min(a, abs(753-n));
    }
    cout << a;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MOD = 1e9+7;
const double PI  = 3.14159265358;
const double eps = 1e-8;
 
#define INF 2147483647
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define RESET(v) memset(v,0,sizeof(v))
#define EB emplace_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep1n(i,n)	for(int i=1;i<n;i++)
#define IOS ios::sync_with_stdio(false);cin.tie();cout.tie();
 
#define MXN 1000000 //10^6
 
int main(){
	ll n, a[70];
	unsigned long long ipt;
	bitset<62> bt;
	
	RESET(a);
	cin>>n;
	rep(i,n){
		cin>>ipt;
		bt = ipt;
		rep(j, 62)
			if(bt[j])	a[j]++;
	}
	
	long long ans = 0, sum, k;
	k = 1;
	rep(i, 62){
		sum = (((n - a[i]) * a[i]) % MOD)*(k%MOD);
		ans += sum%MOD;
		ans %= MOD;
		k <<= 1;
	}
	cout<<ans<<'\n';
	
}

Measured memory_bytes: 256
#include <stdio.h>
//#include <utility>
#include <algorithm>
#include <vector>
//#include <vector>
//#include<string>

using namespace std;

int main() {

	
	int n, maxofa = -1, secondmaxofa = -1;
	vector<int> a(200000);
	int ismaxonlyone = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
		maxofa = max(maxofa, a[i]);
	}

	for (int i = 0; i < n; ++i) {
		if (maxofa == a[i])++ismaxonlyone;
		else secondmaxofa = max(a[i], secondmaxofa);
	}
	
	for (int i = 0; i < n; ++i) {
		if (ismaxonlyone < 2) {
			if (maxofa == a[i])printf("%d\n", secondmaxofa);
			else printf("%d\n", maxofa);
		}
		else {
			printf("%d\n", maxofa);
		}
	}

	return 0;
}

Measured memory_bytes: 2432
#include<bits/stdc++.h>
using namespace std;
int mod=1000000007;
vector<int> v[100001];
int n;
long long wdp[100001],bdp[100001];
void dfs(int a,int p){
	//cout<<v[a].size()<<" ";
	for(int i=0;i<v[a].size();i++){
		if(v[a][i]!=p){
			dfs(v[a][i],a);
			wdp[a]=((wdp[a]%mod)*(((bdp[v[a][i]]%mod)+(wdp[v[a][i]]%mod))%mod)%mod)%mod;
			bdp[a]=((bdp[a]%mod)*(wdp[v[a][i]]%mod))%mod;
		}
	}
	
}
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin>>n;
	for(int i=0;i<n-1;i++){
		int a,b;
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	memset(wdp,0,sizeof(wdp));
	memset(bdp,0,sizeof(bdp));
	for(int i=0;i<=n;i++){
		wdp[i]=1;bdp[i]=1;
	}
	dfs(1,-1);
	//cout<<wdp[3]<<" "<<bdp[3]<<" ";
	cout<<(wdp[1]+bdp[1])%mod;
}

Measured memory_bytes: 12800
n = int(input())
ary = list(map(int, input().split()))
count = 1
for i in range(1, n):
    flag = True
    pointed_mountain = ary[i]
    for another_mountain in ary[:i]:
        if another_mountain > pointed_mountain:
            flag = False
            break
    if flag:
        count += 1

print(count)

Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int N = 1e6+10;
typedef long long LL;
const LL mod = 1e9+7;
LL a[N];

int main()
{

    int n;
    LL x;
    scanf("%d %lld", &n, &x);
    for(int i=1;i<=n;i++) scanf("%lld", &a[i]);
    LL sum=0;
    for(int i=1;i<n;i++)
    {
        if(a[i]+a[i+1]>x)
        {
            sum+=(a[i]+a[i+1]-x);
            if(a[i+1]>=a[i]+a[i+1]-x)
            {
                a[i+1]-=(a[i]+a[i+1]-x);
            }
            else a[i+1]=0;
        }
    }
    printf("%lld\n",sum);
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
  std::string s, t;

int fn(int offset) {
  int count = 0;
  for (int i = offset; i < t.size() + offset; ++i) {
    if (s[i] != t[i - offset]) count++;
  }
  return count;
}

int main() {
  std::cin >> s >> t;

  int best = fn(0);
  for (int i = 0; i < s.size() - t.size(); ++i) {
    best = std::min(best, fn(i));
  }
  printf("%d\n", best);
}


Measured memory_bytes: 3768
//            ____             ____
//           /@@@@\           |@@@@|      ____
//          /@@@@@@\          |@@@@|     |@@@@|
//         /@@@@@@@@\         |@@@@|   __|@@@@|___    ____       ____      ___  _________     ____        ____    ____________      ___  _________     ____         ____
//        /@@@@/\@@@@\        |@@@@|   @@@@@@@@@@@   |@@@@|     |@@@@|    |@@@\/@@@@@@@@@\   (@@@@\      /@@@@)  /@@@@@@@@@@@@|    |@@@\/@@@@@@@@@\   (@@@@\       /@@@@)
//       /@@@@/  \@@@@\       |@@@@|     |@@@@|      |@@@@|     |@@@@|    |@@@@|    \@@@@@|   \@@@@\    /@@@@/  |@@/     |@@@@|    |@@@@|    \@@@@@|   \@@@@\     /@@@@/
//      /@@@@(____)@@@@\      |@@@@|     |@@@@|      |@@@@|     |@@@@|    |@@@@|     |@@@@|    \@@@@\  /@@@@/            |@@@@|    |@@@@|     |@@@@|    \@@@@\   /@@@@/
//     /@@@@@@@@@@@@@@@@\     |@@@@|     |@@@@|      |@@@@|     |@@@@|    |@@@@|     |@@@@|     \@@@@\/@@@@/    /@@@@@@@@@@@@@|    |@@@@|     |@@@@|     \@@@@\ /@@@@/
//    /@@@@@@@@@@@@@@@@@@\    |@@@@|     |@@@@|___   |@@@@|____/@@@@@|    |@@@@|     |@@@@|      \@@@@@@@@/    (@@@@(   )@@@@@|    |@@@@|     |@@@@|      \@@@@|@@@@/
//   /@@@@/          \@@@@\   |@@@@|     |@@@@@@@@    \@@@@@@@@@@@@@@|    |@@@@|     |@@@@|       \@@@@@@/      \@@@@\_/@@@@@@|    |@@@@|     |@@@@|       \@@@@@@@/
//  /@@@@/            \@@@@\  |@@@@|      \@@@@@@/      \@@@@@/  \@@@|    |@@@@|     |@@@@|        )@@@@/        \@@@@@@@/\@@@|    |@@@@|     |@@@@|        \@@@@@/
//                                                                                                (@@@@/

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

//-----------------------------------------------
#define all(x)  x.begin(), x.end()
#define sz(x)   (int)x.size()
#define sq(x)   (x) * (x)
#define fr      first
#define sc      second
//-----------------------------------------------
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pli = pair<ll, int>;

const int N = 300 * 1000 + 5;
const ll mod = 1000000007;
const ll INF = 1000000000 * 1ll * 1000000000 + 500000;
const ld pi = acosl(-1.0);

ll a[N], s[N];
int n;

void input() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    s[n] = 0;
    for (int i = n - 1; i >= 0; i--) {
        s[i] = (s[i + 1] + a[i]) % mod;
    }
}

void solve(int testId) {
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans = (ans + a[i] * 1ll * s[i + 1]) % mod;
    }
    cout << ans << endl;
}

int main() {
    // freopen("test", "r", stdin);
    int testcases = 1;
    // scanf("%d", &testcases);
    for(int testId = 1; testId <= testcases; testId++) {
        input();
        solve(testId);
    }
    return 0;
}


Measured memory_bytes: 6700
#include <iostream>

using namespace std;

int main()
{
    long long n,i;
    cin>>n;
    long long s[n+5];
    for(i=1;i<=n;i++)
        cin>>s[i];
    long long max1=s[1],x=0;
    for(i=1;i<=n;i++)
    {
       if(max1>=s[i])
       {
           x=x+max1-s[i];
       }
       else
       {
           max1=s[i];
       }
    }
    cout<<x<<endl;
    return 0;
}


Measured memory_bytes: 5124
function main()
A,B,C,D,E,F=map(x->parse(Int,x),split(readline()))
X=[false for _=0:F]
Y=[false for _=0:F]
for i=0:F
    for j=0:F
	if i==j==0
		continue
	end
	if 100A*i+100B*j<=F
	X[100A*i+100B*j+1]=true
      else
        break
      end
    end
    end
    for i=0:F
    for j=0:F
	if i==j==0
		continue
	end
	if C*i+D*j<=F
		if F*E>=(C*i+D*j)100;Y[C*i+D*j+1]=true;end
        else
          continue
        end
        end
end
a=100A
b=0
for x=0:F
	if !X[x+1] continue end
    for y=0:F-x
    if Y[y+1]
    if x*E>=100y
    if (x+y)b<y*a
    a,b=x+y,y
    end
    else continue end
    end
    end
end
println("$a $b")
end
main()


Measured memory_bytes: 156492
#include <iostream>
#include <vector>

using namespace std;

int main() {
  int sLength;
  string s;
  string t;
  cin >> sLength;
  cin >> s >> t;
  string result;
  for (int i = 0; i < sLength; i++) {
    result += s.at(i);
    result += t.at(i);
  }
  cout << result << endl;

  return 0;
}

Measured memory_bytes: 256
N = int(input())
X = list(map(int, input().split()))

x = sorted(X)
ans_1 = x[N // 2 - 1]
ans_2 = x[N // 2]

ans = []
for i in range(N):
    if X[i] <= ans_1:
        ans.append(ans_2)
    else:
        ans.append(ans_1)

print(*ans, sep="\n")

Measured memory_bytes: 26772
#include<stdio.h>

int main(){
    int n, k, total = 1, s=0, m=0;
    scanf("%d", &n);
    scanf("%d", &k);
    for (int i = 0; i < n; i++){
            s = total + k;
            m = total * 2;
            if (s >= m)
                total = m;
            if (m > s)
                total = s;
    }
    printf("%d\n", total);
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)
//g++ -std=c++11 
#define OFFSET 12802

using namespace std;

//赤-青        //pos
bool memo[85][85][25610];
long long A[85][85];
long long B[85][85];

long long H, W;


int main(){
	cin >> H >> W;
	rep(h, H) rep(w, W) cin >> A[h][w];
	rep(h, H) rep(w, W) cin >> B[h][w];

	memo[0][0][OFFSET] = true;
	long long ans = LONG_MAX;
	rep(h, H) {
		rep(w, W) {
			rep(num, 25610){
				if(!memo[h][w][num])continue;
				if(h == H-1 && w == W-1) {
					ans = min(ans, abs(num + A[h][w] - B[h][w] - OFFSET));
					ans = min(ans, abs(num + B[h][w] - A[h][w] - OFFSET));
				}
				//Aを赤, Bを青
				memo[h+1][w][num + A[h][w] - B[h][w]] = true;
				memo[h][w+1][num + A[h][w] - B[h][w]] = true;

				//Aを青, Bを赤
				memo[h+1][w][num + B[h][w] - A[h][w]] = true;
				memo[h][w+1][num + B[h][w] - A[h][w]] = true;
			}
		}
	}
	cout << ans << endl;


}



Measured memory_bytes: 111488
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int h, w;
  cin >> h >> w;
  vector<bool> row(h, false);
  vector<bool> col(w, false);
  vector<vector<char>> vec(h, vector<char>(w));
  for (int i = 0; i < h; i++)
  {
    for (int j = 0; j < w; j++)
    {
      cin >> vec.at(i).at(j);
    }
  }

  for (int i = 0; i < h; i++)
  {
    for (int j = 0; j < w; j++)
    {
      if (vec.at(i).at(j) == '#')
      {
        row.at(i) = true;
        col.at(j) = true;
      }
    }
  }
  for (int i = 0; i < h; i++)
  {
    if (row.at(i))
    {
      for (int j = 0; j < w; j++)
      {
        if (col.at(j))
        {
          cout << vec.at(i).at(j);
        }
      }
      cout << endl;
    }
  }
}

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

#define fst first
#define snd second
#define ll long long
#define ld long double
#define pb push_back
#define emp emplace_back
#define pii pair<int, int>
#define usg unsigned
#define sg signed
#define mp make_pair

using namespace std;

void setIO(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
}

const ld PI = 4*atan((ld)1);
const ll INF = 1e18;
const int mxn = 2e5+7;

ll a[mxn], b[mxn];

int main(){
	setIO();
	int n, m, x, ct = 0;
	ll sum = 0;
	cin >> n >> m >> x;
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	for (int i = 0; i < m; i++){
		cin >> b[i];
	}
	int i = 0, j = 0;
	while (i < n && sum+a[i] <= x){
		sum += a[i];
		i++;
	}
	ct = i;
	while (j < m && i >= 0){
		sum += b[j];
		j++;
		while (sum > x && i > 0){
			i--; sum-=a[i];
		}
		if (sum <= x && i+j > ct) ct = i+j;
	}
	cout << ct << endl;
}

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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/02/15  Problem: 075_abc_d / Link: https://abc075.contest.atcoder.jp/tasks/abc075_d?lang=en  ----- */
/* ------問題------

2次元座標上に N 個の点があります。
i(1≦i≦N) 番目の点の座標は (xi,yi) です。
長方形の内部に N 点のうち K 個以上の点を含みつつ、それぞれの辺がX軸かY軸に平行な長方形を考えます。
このとき、長方形の辺上の点は長方形の内部に含みます。
それらの長方形の中で、最小の面積となるような長方形の面積を求めてください。

-----問題ここまで----- */
/* -----解説等-----

O(N^5)、すき
適当にやって通ってしまったけど範囲内にある点の数は毎回計算する余裕がないのなら、
これは事前に計算可能で、二次元累積和でできる。

----解説ここまで---- */

LL N,K;

LL ans = 0LL;

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

	cin >> N>>K;
	VL x(N), y(N);
	VL xc(N), yc(N);
	FOR(i, 0, N) {
		cin >> x[i] >> y[i];
		xc[i] = x[i];
		yc[i] = y[i];
	}

	SORT(xc);
	SORT(yc);
	ans = (xc[N-1]- xc[0])*(yc[N - 1] - yc[0]);
	FOR(u1, 0, N) {
		FOR(u2, u1+1, N) {
			FOR(d1, 0, N) {
				FOR(d2, d1+1, N) {
					LL X = xc[u2] - xc[u1];
					LL Y = yc[d2] - yc[d1];
					int cnt = 0;
					FOR(i, 0, N) {
						if (xc[u1] <= x[i]
							&& x[i] <= xc[u2]
							&&yc[d1] <= y[i]
							&& y[i] <= yc[d2]
							)
							cnt++;
					}

					if (cnt >= K) {
						ans = min(ans, X*Y);
					}



				}
			}
		}
	}

	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 256
from itertools import count, takewhile
from functools import lru_cache

@lru_cache(maxsize=None)
def dfs(n):
  if n < 6:
    return n
  max9 = max(takewhile(lambda x: x<=n, (9**i for i in count())))
  max6 = max(takewhile(lambda x: x<=n, (6**i for i in count())))
  return min(dfs(n-max9), dfs(n-max6))+1
 
print(dfs(int(input())))

Measured memory_bytes: 3572
#include<stdio.h>

int main(){
    char s[100001];
    scanf("%s",s);

    int sum=0;
    for(int i=0;s[i+1]!='\0';i++){
        if(s[i]!=s[i+1]){
            sum++;
        }
    }
    printf("%d\n",sum);
    return 0;
}

Measured memory_bytes: 1816