akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
 
const ll INF = 1LL<<62;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using Graph = vector<vector<int>>;

typedef pair<int, int> P;
typedef priority_queue<int, vector<int>, greater<int>> PQ;
const int MOD = 1000000007;

const int max_a = 20005;

struct mint {
    ll x;
    mint(ll x=0):x((x%MOD+MOD)%MOD){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += MOD-a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime MOD
    mint inv() const {
        return pow(MOD-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
// 2項係数を求める
struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1),ifact(n+1) {
        assert(n < MOD);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};

//nが非常に大きく、aが小さい場合
mint choose(int n, int a){
    mint x = 1, y = 1;
    rep(i,a){
        x *= n-i;
        y *= i+1;
    }
    return x/y;
}

int main(){
    int H1,M1,H2,M2,K;
    cin >> H1 >> M1 >> H2 >> M2 >> K;

    int diff = H2*60 + M2 - (H1*60+M1);

    cout << diff - K << endl;
}

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

long long int n,ans,x,m,i,a;

signed main()
{
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;ans=0;m=trunc(sqrt(n));
	for (i=2;i<m+1;i++)
	{
		x=0;
		while (n%i==0) n=n/i,x++;
		a=0;
		while ((a+2)*(a+1)<=2*x) a++;
		ans=ans+a;
	}
	if (n!=1) ans++;
	cout<<ans;
}


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

static const long long max_sum_value = 1e6;

int main(){

    long long N, W;
    cin >> N >> W;
    vector<long long> w(N), v(N);
    for(int i = 0; i < N; i++) cin >> w[i] >> v[i];

    vector<vector<long long> > dp(N + 1, vector<long long>(max_sum_value + 1, 1e12));
    dp[0][0] = 0;

    for(long long i = 0; i < N; i++){
        for(long long j = 0; j < max_sum_value; j++){
            if(v[i] <= j) dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i]);
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
        }
    }    

    long long ans = 0;
    for(long long i = 0; i < max_sum_value; i++) if(dp[N][i] <= W) ans = i;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 797440
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  int N;
  cin >> N;
  vector<int> s(N);
  int score = 0;
  for (int i = 0; i < N; i++) {
    cin >> s[i];
    score += s[i];
  }
  if (score % 10 != 0) {
    cout << score << endl;
    return 0;
  }
  sort(s.begin(), s.end());
  int tmp = 999;
  for (int i = 0; i < N; i++) {
    if (s[i] % 10 != 0) {
      tmp = i;
      break;
    }
  }
  if (tmp == 999) cout << 0 << endl;
  else cout << score - s[tmp] << endl;
}


Measured memory_bytes: 3624
#include<stdio.h>
long long gcd(long long a,long long b){
	if(b!=0)   gcd(b,a%b);
	else  return a;
}
long long lcm(long long a,long long b){
	return a/gcd(a,b)*b;
}
int main(void){
  long long n,t,s,b,i;
  scanf("%lld",&n);
 for(i=1;i<=n;i++){
 	scanf("%lld",&t);
 	if(i==1)
 	s=t;
 	else
 	s=lcm(s,t);
 }
  printf("%lld\n",s);
  return 0;
}

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

using namespace std;

bool check(const string &s, char c) {
	for (int i = 0; i < (int)s.size(); i++) {
		if (s[i] != c) {
			return false;
		}
	}
	return true;
}

int solve(string s, char c) {
	int result = 0;

	while (!check(s, c)) {
		string t(s.size() - 1, ' ');

		for (int i = 0; i < (int)t.size(); i++) {
			if (s[i + 1] == c) {
				t[i] = c;
			}
			else {
				t[i] = s[i];
			}
		}

		swap(s, t);

		result++;
	}

	return result;
}

int main() {

	string s;
	int result;

	cin >> s;
	result = s.size();
	for (char c = 'a'; c <= 'z'; c++) {
		result = min(result, solve(s, c));
	}

	cout << result << "\n";

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int (i) = 0; (i) < (n); (i)++)
using namespace std;
typedef long long ll;
// Welcome to my source code!

#define MAX 100000
#define SENTINEL 2000000000

struct Card { char suit; int num; };

Card L[MAX / 2], R[MAX / 2];

void merge(Card B[], int left, int mid, int right) {
    int n1 = mid - left;
    int n2 = right - mid;
    rep(i,n1) L[i] = B[left + i];
    rep(i,n2) R[i] = B[mid + i];
    L[n1].num = R[n2].num = SENTINEL;
    int i = 0, j = 0;
    for (int k = left; k < right; k++) {
        if (L[i].num <= R[j].num) B[k] = L[i++];
        else B[k] = R[j++];
    }
}

void mergeSort(Card B[], int left, int right) {
    if (left + 1 < right) {
        int mid = (left + right) / 2;
        mergeSort(B, left, mid);
        mergeSort(B, mid, right);
        merge(B, left, mid, right);
    }
}

int partition(Card A[], int p, int r) {
    Card t;    
    int x = A[r].num;
    int i = p-1;
    for (int j = p; j < r; j++) {
        if (A[j].num <= x) {
            i++;
            t = A[i]; A[i] = A[j]; A[j] = t;
        }
    }
    t = A[i+1]; A[i+1] = A[r]; A[r] = t;
    return i+1;
}

void quickSort(Card A[], int p, int r) {
    if (p < r) {
        int q = partition(A, p, r);
        quickSort(A, p, q-1);
        quickSort(A, q+1, r);
    }
}

int main() {
    int n, num;
    char suit;
    cin >> n;
    Card A[n], B[n];

    rep(i,n) {
        cin >> suit >> num;
        A[i].suit = B[i].suit = suit;
        A[i].num = B[i].num = num;
    }

    quickSort(A, 0, n-1);
    mergeSort(B, 0, n);

    rep(i,n) {
        if (A[i].suit != B[i].suit) {
            cout << "Not stable" << endl;
            break;
        }
        if (i == n-1) cout << "Stable" << endl;
    }

    rep(i,n) {
        cout << A[i].suit << ' ' << A[i].num << endl;
    }
}


Measured memory_bytes: 5436
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
  int n, m, s;
  double sx[501], sy[501], sz[501], tx, ty, tz, tr, u, v, w;
  bool f[501];

  while(cin>>n && n){
    s = 0;
    for(int i = 0; i < n; i++){
      cin >> sx[i] >> sy[i] >> sz[i];
      f[i] = true;
    }
    cin >> m;
    while(m--){
      cin >> tx >> ty >> tz >> tr;
      v = sqrt(tx*tx+ty*ty+tz*tz);

      for(int i = 0; i < n; i++){
	u = sqrt(sx[i]*sx[i]+sy[i]*sy[i]+sz[i]*sz[i]);
	w = tx*sx[i] + ty*sy[i] + tz*sz[i];

	if(acos(w/(v*u)) <= tr && f[i]){
	  s++;
	  f[i] = false;
	}
      }
    }

    cout << s << endl;
  }

  return 0;
}

Measured memory_bytes: 992
# -*- coding: utf-8 -*-
n = int(input())
s = input()

def _rot(c, n):
    if 'A' <= c and c <= 'Z':
        return chr((ord(c) - ord('A') + n) % 26 + ord('A'))
    if 'a' <= c and c <= 'z':
        return chr((ord(c) - ord('a') + n) % 26 + ord('a'))
    return c

def rotn(s, n):
    # ジェネレータ内包表記で文字列に ROT13 を適用する
    g = (_rot(c, n) for c in s)
    # 文字列に直す
    return ''.join(g)

print(rotn(s, n))


Measured memory_bytes: 39792
# C - Peaks
def main():
    N, M, *HAB = map(int, open(0).read().split())
    H, AB = [0] + HAB[:N], HAB[N:]
    good_observatories = set(range(1, N + 1))
    for a, b in zip(*[iter(AB)] * 2):
        if H[a] >= H[b]:
            good_observatories.discard(b)
        if H[b] >= H[a]:
            good_observatories.discard(a)
    print(len(good_observatories))


if __name__ == "__main__":
    main()


Measured memory_bytes: 44040
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

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

int ans, dp[4001][4001];

int main() {
	while (true) {
		ans = 0;
		memset(dp, 0, sizeof(dp));
		string str[2];
		cin >> str[0];
		if (str[0].empty()) break;
		cin >> str[1];
		REP(i, (int)str[0].size()) {
			REP(j, (int)str[1].size()) {
				if (str[0][i] == str[1][j]) {
					dp[i + 1][j + 1] = dp[i][j] + 1;
					ans = ans < dp[i + 1][j + 1] ? dp[i + 1][j + 1] : ans;
				}
				else dp[i + 1][j + 1] = 0;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 63748
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int,int>;

vector<int>bitSearch(int bit,int n){
    vector<int>S;
    rep(i,n)if(bit&(1<<i))S.push_back(i);
    return S;
}



int main(){
    vector<string>s(3);
    rep(i,3)cin>>s[i];
    rep(i,3)cout<<s[i][i];
}



Measured memory_bytes: 256
N = int(input())
T = [int(input()) for _ in range(N)]
  
 # 最大公約数
def gcd(a, b):
   while b > 0:
      a, b = b, a%b
   return a
  
 # 最小公倍数
def lcm(a, b):
   return a*b//gcd(a, b)
  
 # 逐次的にlcmを計算する
ans = T[0]
for i in range(N):
    ans = lcm(ans, T[i])
    
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for(ll i=(ll)a; i<(ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
#ifdef DEBUG
#include "../program_contest_library/memo/dump.hpp"
#else
#define dump(...)
#endif
constexpr ll INF = 1LL<<60;

int main() {
    ll x;
    cin >> x;

    ll ret = 0;
    using R = long double;
    ll now = 100;
    while(now < x) {
        now *= 1.01;
        ret++;
    }

    cout << ret << endl;

    return 0;
}


Measured memory_bytes: 3620
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
ans = 0

before = -10
for i in range(N):
    ans += B[A[i] - 1]
    if before + 1 == A[i]:
        ans += C[before -1]
    before = A[i]

print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <utility>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <cmath>

#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vec vector
#define INF (int)1e9
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
#define PI 3.1415926535
typedef long long int ll;
typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};

using namespace std;

int main(){
    ll x,y;
    cin>>x>>y;
    
    if(x*y==0){
        if(x<y)cout<<y-x<<endl;
        else cout<<x-y+1<<endl;
    }else if(x*y>0){
        if(x<y)cout<<y-x<<endl;
        else cout<<abs(abs(x)-abs(y))+2<<endl;
    }else {
        cout<<abs(abs(x)-abs(y))+1<<endl;
    }

    return 0;
}

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

int main(){
   string s;
   cin >> s;
   for(int i=0;i<s.size();i++){
      if(s.at(i)=='A'||s.at(i)=='T'||s.at(i)=='G'||s.at(i)=='C'){
         s.at(i)='$';
      }
   }
   int a,b;
   int max=0;
   int j=0;
   for (int i=0;i<s.size();i++){
      if(s.at(i)=='$'){
         a=i;
         j=i;
         while(s.at(j)=='$'){
            b=j;
            if(j==s.size()-1)break;
            j++;
         }
         if(max<b-a+1)max=b-a+1;
         i=j;
      }
   }
   cout << max << endl;
}

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

typedef unsigned int uint;
typedef long long llong;
typedef unsigned long long ullong;
// -2.1e-9 <= int <= 2.1e9
// -9.2e-18 <= long long <= 9.2e18
// 0 <= unsigned int <= 4.2e9
// 0 <= unsigned long long <= 18.4e18

int main()
{
    int L; cin >> L;
    double ans = (L * L * L) / (3.0 * 3.0 * 3.0);
    cout << fixed << setprecision(9);
    cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String ss = sc.next();
		String[] s = ss.split("");
		String ts = sc.next();
		String[] t = ts.split("");
		int count = 0;
		for (int i = 0; i < 3; i++) {
			if (s[i].equals(t[i])) {
				count++;
			}
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#include <numeric>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REP1(i, n) for(int i = 1; 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 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main() {
	int a, b, c, d; cin >> a >> b >> c >> d;
	if (a + b > c + d) {
		cout << "Left" << endl;
	}
	else if (a + b == c + d) {
		cout << "Balanced" << endl;
	}
	else if (a + b < c + d) {
		cout << "Right" << endl;
	}
}

Measured memory_bytes: 3604
#include<iomanip>
#include <string>
#include<iostream>
#include<vector>
#include <bits/stdc++.h>
#include <stdio.h>
#include <numeric>
#include<math.h>
#include <ctype.h>
#include <algorithm> // sort
#include <map> // pair
using namespace std;
#define nin(n) int n; cin >> n;
#define kin(k) int k; cin >> k;
int n;

int a,b,c;

vector<int> vec;

int dfs(int cur,int x,int y,int z){
    if(cur==n){
      if(min(min(x,y),z)>0){
        return abs(x-a)+abs(y-b)+abs(z-c)-30;
      }
      else{
        return 10000000;
      }
    }
    else{
     int p=dfs(cur+1,x,y,z);
     int q=dfs(cur+1,x+vec.at(cur),y,z)+10;
     int r=dfs(cur+1,x,y+vec.at(cur),z)+10;
     int s=dfs(cur+1,x,y,z+vec.at(cur))+10;
      return min(min(min(p,q),r),s);
    }
}
const int INF = 1001001001;
int main(){
  cin >>n;cin >> a >>b >>c;
  vec.resize(n);
  for(int i=0;i<n;i++){
    cin >> vec.at(i);
  }
  cout << dfs(0,0,0,0);
}
    
  

Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

int M;
string s[10000];
string t;
int l, r;

int main(){
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> s[i];
	}
	cin >> t;
	l = 1;
	r = 1;
	for (int i = 0; i < M; i++) {
		string box = s[i];
		for (auto j = box.begin(); j != box.end(); ++j) {
			if (*j == '?')*j = 'a';
		}
		if (t >= box) {
			r++;
		}
		box = s[i];
		for (auto j = box.begin(); j != box.end(); ++j) {
			if (*j == '?')*j = 'z';
		}
		if (t > box)l++;
	}
	for (int i = l; i < r; i++)cout << i << " ";
	cout << r << endl;
	return 0;
}


Measured memory_bytes: 896
n=int(input())
DP=[i for i in range(100001)]
for i in range(100001):
    p=1
    while p<=i:
        DP[i]=min(DP[i],DP[i-p]+1)
        p*=6
    p=1
    while p<=i:
        DP[i]=min(DP[i],DP[i-p]+1)
        p*=9
print(DP[n])

Measured memory_bytes: 7064
#include <iostream>
#include <stdio.h>
using namespace std;
long long n,m;
int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    m =(long long)std::max((long long)a*c,(long long)a*d);
    n =(long long)std::max((long long)b*c,(long long)b*d);
   printf("%lld",std::max(m,n));
    return 0;
}


Measured memory_bytes: 3772
#include<stdio.h>
#include<stdlib.h>
#define max(p,q)((p)>(q)?(p):(q))

int a[100010];
void f(int l,int r,int k){
	if(l==r)return;
	if(a[r-1]==k){
		putchar('(');
		f(l,r-1,k+1);
		putchar(')');
		return;
	}
	int M=0;
	for(int i=l;i<r-1;i++){
		M=max(M,a[i]);
		if(M-k==i-l){
			f(l,i+1,k);
			f(i+1,r,M+1);
			return;
		}
	}
	puts(":(");
	exit(0);
}

int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",a+i);
	f(0,n,1);
	puts("");
}


Measured memory_bytes: 2120
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<set>
#include<complex>
#include<string>
#include<cstring>
using namespace std;
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 100000000
#define debug(x) cout<<#x<<": "<<x<<endl

#define all(x) x.begin(),x.end()
typedef pair<int,int> P;
typedef pair<int,P> PP;

int h,w;
int n;
int a[10005];
int hh,ww;
int ans[104][104];
int main()
{
	cin>>h>>w;
	cin>>n;
	rep(i,n)
	{
		cin>>a[i];
	}
	rep(i,n)
	{
		while(a[i]!=0)
		{
			a[i]--;
			ans[hh][ww]=i+1;
			ww++;
			if(ww==w)
			{
				hh++;
				ww=0;
			}
		}
	}
	rep(i,h)
	{
		if(i%2==0)
		{
			rep(j,w)
			{
				cout<<ans[i][j];
				if(j!=w-1)cout<<" ";
				else cout<<endl;
			}
		}
		else
		{
			rep(j,w)
			{
				cout<<ans[i][w-1-j];
				if(j!=w-1)cout<<" ";
				else cout<<endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 384
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<string> r = {
	"Rock",
	"Gun",
	"Lightning",
	"Devil",
	"Dragon",
	"Water",
	"Air",
	"Paper",
	"Sponge",
	"Wolf",
	"Tree",
	"Human",
	"Snake",
	"Scissors",
	"Fire"
};
int n; string s;
int main() {
	while (cin >> n, n) {
		vector<int> v;
		for (int i = 0; i < n; i++) {
			cin >> s;
			v.push_back(find(r.begin(), r.end(), s) - r.begin());
		}
		string ret = "Draw";
		for (int i = 0; i < v.size(); i++) {
			bool win = false, lose = false;
			for (int j = 0; j < v.size(); j++) {
				if (i == j) continue;
				int z = (v[j] - v[i] + 15) % 15;
				if (1 <= z && z <= 7) lose = true;
				if (8 <= z && z <= 14) win = true;
			}
			if (win && !lose) ret = r[v[i]];
		}
		cout << ret << endl;
	}
	return 0;
}

Measured memory_bytes: 3136
#include<bits/stdc++.h>
#define LL long long
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPA(i,n) for(int i=1;i<(n);++i)
#define PII pair<int,int>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define PDD pair<double, double>
#define MOD ((int)2e9 + 7)
#define INF ((int)2e9)
#define INFLL ((LL)2e18)
#define ALL(x) (x).begin(),(x).end()
#define ctoi(x) (x - 'a') 
#define CTOI(x) (x - 'A')
#define BIT(x) (2 << (x))
using namespace std;

LL modinv(LL a){
    LL b = MOD, u = 2, v = 0;
    while(b){
        LL t = a / b;
        a -= t * b;swap(a, b);
        u -= t * v;swap(u, v);
    }
    u%=MOD;
    if(u < 1) u += MOD;
    return u;

}

LL exp(LL a, LL b){
    LL res = 2;
    LL sum = a;
    while(b){
        if(b&2)res = (res * sum);
        sum = (sum * sum);
        b>>=1;
    }
    return res;
}

double exp(double a, LL b){
    double res = 1;
    double sum = a;
    while(b){
        if(b&1)res = (res * sum);
        sum = (sum * sum);
        b>>=1;
    }
    return res;
}

PII operator+(const PII &a, const PII &b){
    return PII(a.first + b.first, a.second + b.second);
}

vector<vector<int> > xc(100001), yc(100001);

PII func(PII p){
    PII res(0, 0);
    if(!xc[p.first].empty()){
        vector<int> line = xc[p.first];
        xc[p.first].clear();
        ++res.first;
        for(auto &i:line){
            res = res + func(PII(p.first, i));
        }
    }
    if(!yc[p.second].empty()){
        vector<int> line = yc[p.second];
        yc[p.second].clear();
        ++res.second;
        for(auto &i:line){
            res = res + func(PII(i, p.second));
        }
    }
    return res;
}

signed  main(){
    int a, b, c;
    cin >> a >> b >> c;
    if(b>=c)cout << "delicious" << endl;
    else if(c<=a+b)cout << "safe" << endl;
    else cout << "dangerous" << endl;
    return 0;
}



Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}

signed main() {
    int N, K, C;
    string S;
    cin >> N >> K >> C;
    cin >> S;


    //L[x]:x回目に働く日はL[x]日目以降
    //R[x]:x回目に働く日はR[x]日目以前（最後に反転）
    //L[x]=R[x]であれば、L[x](R[x])日目は必ず働く
    vi L, R;
    rep(i, N) {
        if(S[i]=='o') {
            L.pb(i);
            if(L.size()==K) break;
            i+=C;
        }
    }
    rep(i, N) {
        if(S[N-1-i]=='o') {
            R.pb(N-1-i);
            if(R.size()==K) break;
            i+=C;
        }
    }

    reverse(ALL(R));
    vi res;
    rep(i, K) {
        if(L[i]==R[i]) res.pb(L[i]+1);
    }

    rep(i, res.size()) {
        cout << res[i] << endl;
    }
    
    return 0;
}

Measured memory_bytes: 6644
#include<iostream>
#include<complex>

#define EPS 1e-3

using namespace std;

typedef complex<double> P;

double cross(P v1,P v2){
	return v1.real()*v2.imag()-v1.imag()*v2.real();
}

bool che(P v1,P v2,P v3,P v){
	if(cross(v2-v1,v-v1)<-EPS&&cross(v3-v2,v-v2)<-EPS&&cross(v1-v3,v-v3)<-EPS)return true;
	else if(cross(v2-v1,v-v1)>EPS&&cross(v3-v2,v-v2)>EPS&&cross(v1-v3,v-v3)>EPS)return true;
	return false;
}

int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		P v1,v2,v3;
		P k,s;
		cin>>v1.real()>>v1.imag()>>v2.real()>>v2.imag()>>v3.real()>>v3.imag()>>k.real()>>k.imag()>>s.real()>>s.imag();
		
		if(che(v1,v2,v3,k)^che(v1,v2,v3,s)==1)cout<<"OK"<<endl;
		else cout<<"NG"<<endl;
	}
}

Measured memory_bytes: 1220
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE ScopedTypeVariables #-}


import GHC.TypeLits
import Data.Int
import Data.Proxy
import qualified Data.Map.Lazy as Map
import Control.Monad
import Control.Monad.State
import Data.List

data Mint (m :: Nat) = Mint {getMintValue :: Integer} deriving (Eq, Show)

makeMint :: forall p. KnownNat p => Integer -> Mint p
makeMint a = Mint $ fromInteger $ a `mod` (natVal (Proxy :: Proxy p))

instance KnownNat p => Num (Mint p) where
  (Mint a) + (Mint b) = makeMint $ a + b
  (Mint a) - (Mint b) = makeMint $ a - b
  (Mint a) * (Mint b) = makeMint $ a * b
  negate (Mint a) = makeMint $ negate a
  abs = id
  signum (Mint a) = if a == 0 then 0 else 1
  fromInteger = makeMint

invMint :: forall p. KnownNat p => Mint p -> Mint p
invMint m = let p = (natVal (Proxy :: Proxy p)) in m ^ (p - 2)



factorize :: Integral a => a -> [(a, Int)]
factorize n = let (m, xs) = divideAll n 2 in if m /= 1 then reverse $ (m, 1) : (reverse xs) else xs
  where
    divide n p
      | n `mod` p == 0 = let (m, c) = divide (n `div` p) p in (m, c+1)
      | otherwise = (n, 0)

    divideAll n p
      | p * p > n = (n, [])
      | otherwise = 
          let
            x @ (m, c) = divide n p
          in
            if c == 0 then
              divideAll m (p+1)
            else
              let (q, xs) = divideAll m (p+1)
              in (q, (p, c) : xs)



type M = Mint 1000000007

main :: IO ()
main = do
  n <- readLn :: IO Int
  a <- map read . words <$> getLine :: IO [Int]

  let l = product .
          map (\xs @ (x:_) -> (fromIntegral (fst x) :: M) ^ (maximum $ map snd xs)) .
          groupBy (\(x, _) (y, _) -> x == y) .
          sort . concat $ (map factorize a)

  let ans = sum $ map ((l *) . invMint . (fromIntegral :: Int -> M)) a

  print $ getMintValue ans


Measured memory_bytes: 25980
from collections import Counter
S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1

#p.append(0)
#ans = 0
#c = Counter(p)
#for k,n in c.most_common():
#  if n > 1:
#    ans += 1
#  else:break
  
print(sum([i*(i-1)//2 for i in p]))

Measured memory_bytes: 9496
import java.util.*;
public class Main {
	Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		new Main();
	}

	public Main(){
		new AOJ0260().doIt();
	}
	
	class AOJ0260{
		long n;
		long[] p,j;
		void solve(){
			Arrays.sort(j);
//			System.out.println(Arrays.toString(j));
			long sum = 0;
			long cnt = n;
			for(int i=0;i<n;i++)sum+=p[i];
			long max = sum*cnt;
			for(int i=(int)n-2;i>=0;i--){
//				System.out.println(sum+" "+cnt+" "+max);
				sum = sum+j[i];
				cnt--;
				long calc = sum*cnt;
//				System.out.println(calc);
				max = Math.max(max, calc);
			}
			System.out.println(max);
		}
		
		void doIt(){
			while(in.hasNext()){
				n = in.nextInt();
				if(n==0)break;
				p = new long[(int)n];
				j = new long[(int)(n-1)];
				for(int i=0;i<n;i++)p[i] = in.nextInt();
				for(int i=0;i<n-1;i++)j[i] = in.nextInt();
				solve();
			}
		}
	}
	
}

Measured memory_bytes: 162784
#include<stdio.h>

int main(void){
	int i, max=0, mid=0, min=0, mount;
	
	for(i=0;i<10;i++){
		scanf("%d", &mount);
		
		if(mount>max){
			min = mid;
			mid = max;
			max = mount;
		}else if(mount>mid){
			min = mid;
			mid = mount;
		}else if(mount>min){
			min = mount;
		}
	}
	
	printf("%d\n",max);
	printf("%d\n",mid);
	printf("%d\n",min);
	
	return 0;
}

Measured memory_bytes: 0
main :: IO()
main = do
  n <- getLine
  (a:as) <- map read . words <$> getLine
  putStrLn $ show $ slv as a 0 

slv :: [Int] -> Int -> Int -> Int
slv [] _ ret = ret
slv (a:as) val ret | val == a = slv as 10000 (ret + 1)
                   | otherwise = slv as a ret 

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

using namespace std;
using ll =long long;

#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}

const ll INF = 1LL << 60;

//Write From this Line

const int mod = 1e9+7;
int main()
{
	string s;
	cin>> s;
	string s1,s2;
	string search = "keyence";
	int co = 7; 
	int depo = -1 ;
	string next_search = "" ;
	string fn = "ecneyek";
	int count = 0;
	int depo2 = 0 ;
	while(1){
		rep(i,s.size()-co+1){
			s1 = s.substr(i,co);
			if(s1 == search){
				depo = i+co ;
				depo2 = i ;
				goto  SKIP ;
			}
		}
		co -- ;
		search.pop_back();
		next_search.push_back(fn[count]);
		count ++ ;
	}
SKIP :
	rSORT(next_search);
	if(next_search.size() == 0){
		cout <<"YES"<<endl;
		return 0 ;
	}
	if(depo2 != 0 ){
		cout << "NO" << endl;
		return 0 ;
	}
	if(s.substr(s.size()-next_search.size(),next_search.size()) == next_search){
		cout << "YES" <<endl;
	}else{
		cout <<"NO"<<endl;
	}
}


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

using namespace std;

#define PB	push_back
#define ALL(x)	(x).begin(), (x).end()
#define ALLR(x)	(x).rbegin(), (x).rend()
#define MP	make_pair

#define debug(args...) { string _s = #args; replace(ALL(_s), ',', ' '); stringstream ss(_s); cerr << endl;_debug(ss, args); }
#define _rg auto it = next(v.begin()); it != v.end(); it++
#define _input ostream& operator <<(ostream& out

template<typename T, typename U>
_input, const pair<T, U>& p) {
	out << "(" << p.first << ", " << p.second << ")";
	return out;
}

#define cont(c) template<typename T> _input, const c<T>& v) { \
					if (v.empty()) return out; \
					out << "[" << *v.begin(); \
					for (_rg) out << ", " << *it; \
					out << "]"; return out; \
				}
				
#define cont2(c) template<typename T, typename U> _input, const c<T, U>& v) { \
					if (v.empty()) return out; \
					out << "[" << *v.begin(); \
					for (_rg) out << ", " << *it; \
					out << "]"; return out; \
				}

cont(vector) cont(set) cont(multiset) cont(queue) cont2(map)

template<typename T, size_t n, typename= enable_if_t<!is_same<T, char>::value>>
_input, const T(&v)[n]) {
	if (n == 0) return out;
	out << "[" << v[0];
	for (int i = 1; i < (int)n; i++) out << ", " << v[i];
	out  << "]"; return out;
}

template<typename T, typename... Ts>
void _debug(stringstream& ss, const T &arg) {
	string name; ss >> name;
	cerr << name << " = " << arg << endl;
}

template<typename T, typename... Ts>
void _debug(stringstream& ss, const T& arg, const Ts&... args) {
	string name; ss >> name; 
	cerr << name << " = " << arg << ", ";
	if (is_class<T>::value || is_array<T>::value) cerr << endl;
	_debug(ss, args...);
}

#define FAST_IO ios::sync_with_stdio(false); cin.tie(0)

#define int long long int

typedef pair<int, int> ii;
typedef pair<pair<int, int>, int> iii;
typedef vector<int> vi;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef unsigned long long ull;

const int INF = LONG_LONG_MAX>>1;
const int NINF = LONG_LONG_MIN/2;
const double PI = 3.141592653589793238;

const int mod = 998244353;

void add_self(int& a, int b) {
	a += b;
	a %= mod;
}

int mul(int a, int b) {
	return ((a%mod) * (b%mod))%mod;
}

int power(int a, int b) {
	a %= mod;
	int r = 1;
	while (b) {
		if (b%2 == 1) {
			r = mul(r, a);
		}
		a = mul(a, a);
		b /= 2;
	}
	return r;
}

int inv(int n) {
	return power(n, mod-2);
}

int32_t main() {
	FAST_IO;
	
	int n, s;
	cin >> n >> s;
	int a[n];
	for (int& x: a) cin >> x;
	
	int dp[n+1][s+1];
	
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= s; j++) {
			dp[i][j] = 0;
		}
	}
	
	dp[0][0] = power(2, n);
	
	int inv2 = 2;
	inv2 = inv(inv2);
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= s; j++) {
			add_self(dp[i+1][j], dp[i][j]);
			if (j + a[i] <= s) {
				add_self(dp[i+1][j+a[i]], mul(dp[i][j], inv2));
			}
		}
	}
	
	cout << dp[n][s] << endl;
}
// g++ -Wall -Wextra -Wshadow -fsanitize=undefined -std=c++17


Measured memory_bytes: 73916
//Bismillahir Rahmanir Rahim
#include <bits/stdc++.h>
using namespace std;

typedef long long              ll;
typedef long double            ld;
typedef pair<int, int>         pi;
typedef vector<int>            vi;
typedef vector<pair<int, int>> vpi;

#define pb       push_back
#define all(x)   begin(x), end(x)
#define sz(x)    (int)(x).size()
#define ff       first
#define ss       second
#define mp       make_pair
#define lb       lower_bound
#define ub       upper_bound
#define tcase()  int t; cin >> t; while(t--)

const int MOD = 1e9 + 7; // 998244353;
const int MX  = 2e5 + 5;
const ll  INF = 1e18;
const ld  PI  = acos((ld) -1);

void setIO(string name = "") {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if(sz(name)){
        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}

int main(){

    setIO();

    int n, l, r;
    cin >> n >> l >> r;

    int dif = r - l - 1;

    int arr[n + 1] = {0};

    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            arr[min({j - i, abs(l - i) + 1 + abs(j - r), abs(r - i) + 1 + abs(j - l)})]++;
        }
    }

    for(int i = 1; i < n; i++) cout << arr[i] << "\n";
}


Measured memory_bytes: 3616
import java.util.*;
import java.io.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Math.*;

public class Main {

	int INF = 1 << 28;
	//long INF = 1L << 62;
	double EPS = 1e-10;
	int d, x, y, n;
	boolean[] a, b;
	int[] p, q;

	void run() {
		Scanner sc = new Scanner(System.in);
		d = sc.nextInt();
		x = sc.nextInt();

		a = new boolean[x];
		p = new int[x];

		for (int i=0;i<x;i++) {
			a[i] = sc.next().equalsIgnoreCase("D");
			p[i] = sc.nextInt();
		}

		y = sc.nextInt();

		b = new boolean[y];
		q = new int[y];

		for (int i=0;i<y;i++) {
			b[i] = sc.next().equalsIgnoreCase("DD");
			q[i] = sc.nextInt();
		}

		n = x + 2 * y;
		mem = new int[1<<n];
//		debug(n, x, y, a, b, p, q);
		fill(mem, -1);

		System.out.println(solve(0));
	}

	int[] mem;
	int solve(int S) {
		if (mem[S] >= 0) return mem[S];
		if (Integer.bitCount(S) == d) return 0;
		int max = 0;

		for (int i=0;i<n;i++) if (((S>>i)&1) == 0) {
			if (i < x) {
				if (! a[i]) continue;
				max = max(max, solve(S|(1<<i)) + p[i]);
			}
			else {
//				debug(i, Integer.bitCount(S));
				if (i % 2 != x % 2) continue;
				if (Integer.bitCount(S) >= d - 1) continue;
				int j = i - x; j /= 2;
				if (! b[j]) continue;
				max = max(max, solve(S|(3<<i)) + q[j]);
			}
		}

		return mem[S] = max;
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}

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

Measured memory_bytes: 26828
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <ctime>
#define INF 999999999
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=(n);i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define MOD(x) (x%(mod))
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool debug=false;
/*---------------------------------------------------*/

int haiku[45];
int num[6]={5,7,5,7,7,0};

void solve(int n){
  int s=0,e=0,cnt=0,sum=haiku[0];
  int dast=0;
  
  rep(i,n-4){
    dast=cnt=0;
    s=e=i;
    sum=haiku[i];
    
    while(s!=n&&e!=n){
      if(debug)cout<<"s: "<<s<<"  e:"<<e<<"  cheack( "<<cnt<<" ): "<<num[cnt]<<"  dast: "<<dast<<"  cnt: "<<cnt<<endl;
      if(cnt==5)break;
      if(sum==num[cnt]){
	s=e=e+1;sum=haiku[s];cnt++;
      }else if(sum<num[cnt]){
	e++;sum+=haiku[e];
      }else if(sum>num[cnt]){
	break;
      }
    }
    if(debug)cout<<endl;
    if(debug)cout<<"s: "<<s<<"  e:"<<e<<"  cheack( "<<cnt<<" ): "<<num[cnt]<<"  dast: "<<dast<<"  cnt: "<<cnt<<endl;
    if(cnt==5){
      cout<<i+1<<endl;
      break;
    } 
  }
}


int main(){
  int n;
  string s;
  while(cin>>n){
    if(n==0)break;
    rep(i,n){cin>>s;haiku[i]=s.size();}
    solve(n);
  }
}

Measured memory_bytes: 3160
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<cmath>

using namespace std;

int main()
{
    long long n,c,i,j;
    cin>>n;
    //scanf("%I64d",&n);
    for(i=1,c=1; i<=n; i++)
    {
        for(j=2; j<=n; j++)
        {
            if(pow(i,j)<=n)
            {
                if(pow(i,j)>c)
                    c=pow(i,j);

            }
            else
                break;
        }
    }
    cout<<c<<endl;
    //printf("%I64d\n",c);
    return 0;
}


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

int main()
{
	string str;
	getline(cin, str);

	for(auto c : str) {
		if(isalpha(c)) 
			cout << (char) (isupper(c) ? tolower(c) : toupper(c));
		else
			cout << c;
	}
	cout << endl;

	return 0;
}



Measured memory_bytes: 3128
//** aman**/
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define dl          double
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define lb lower_bound
#define ub upper_bound
#define bs          binary_search
#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int dis[100005]={0};
vector<pair<int,int>> g[100005];
void dfs(int cu,int pa){
	for(auto uu:g[cu]){
		int u=uu.F,w=uu.S;
		if(u==pa)continue;
		dis[u]=dis[cu]+w;
		dfs(u,cu);
	}
}
int main(){
	int n;cin>>n;
	for(int i=0;i<n-1;i++){
		int x,y,z;cin>>x>>y>>z;
		g[x].pb({y,z});
		g[y].pb({x,z});
	}
	dfs(1,0);
	for(int i=1;i<=n;i++){
		if(dis[i]%2)cout<<"1"<<endl;
		else cout<<"0"<<endl;
	}
}

Measured memory_bytes: 8320
#include<cstdio>
#include<queue>
/*
#include<windows.h>
*/
using namespace std;

struct DATA{
	int y;
	int x;
	int n;
};


bool  vi[1001][1001];
char cp[1001][1001];  
DATA Start,Goal;
int H,W,N;
/*
void pa(){
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			if(vi[i][j])printf("¡");
			else printf(" ");
		}puts("");
	}puts("");
}
*/
int BFS(){
	queue<DATA> Q;
	Q.push(Start);
	
	while(!Q.empty()){
//		pa();
//		system("cls");
		DATA p = Q.front();
		Q.pop();
//		printf("%d (%4d,%4d) %d\n", Q.size(), p.x, p.y, p.n);
		const int dy[] = {1,0,-1,0};
		const int dx[] = {0,1,0,-1};
		
		if(vi[p.y][p.x])continue;
		vi[p.y][p.x] = true;
		if(p.y == Goal.y && p.x == Goal.x)return p.n;
		
		for(int i = 0; i < 4; i++){
			if(p.x+dx[i] < 0 || p.x+dx[i] >= W || p.y+dy[i] < 0 || p.y+dy[i] >= H || cp[p.y][p.x] == 'X' && !vi[p.y+dy[i]][p.x+dx[i]])continue;
			DATA NEXT = {p.y+dy[i],p.x+dx[i],p.n+1};
			Q.push( NEXT );
		}
	}
	return -1;
}

int main(void){
	
	while(scanf("%d %d %d", &H, &W, &N) != EOF ){
		
		char next = '1';
		int ans = 0;
		for(int i = 0; i < H; i++)scanf("%s",cp[i]);
		
		while(next-'1' != N){
			for(int i = 0; i < H; i++){
				for(int j = 0; j < W; j++){
					vi[i][j] = false;
				}
			}
			
			if(next == '1'){
				for(int i = 0; i < H; i++){
					for(int j= 0; j < W; j++){
						if(cp[i][j] == 'S'){
							Start.x = j;
							Start.y = i;
							Start.n = 0;
							goto A;
						}
					}
				}
			}else {
				for(int i = 0; i < H; i++){
					for(int j = 0; j < W; j++){
						if(cp[i][j] == next-1){
							Start.x = j;
							Start.y = i;
							Start.n = 0;
							goto A;
						}
					}
				}
			}
			A:
			
			for(int i = 0; i < H; i++){
				for(int j = 0; j < W; j++){
					if(cp[i][j] == next){
						Goal.x = j;
						Goal.y = i;
						goto B;
					}
				}
			}
			B:
//			printf("S = (%d %d)\n", Start.x, Start.y);
//			printf("G = (%d %d)\n", Goal.x, Goal.y);
			ans += BFS();
			next++;
		}
		printf("%d\n",ans);
	}
	return 0;
}

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

#define M 1000000 /* your task*/
#define L 14

char H[M][L]; /* Hash Table */

int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
}

/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key){ return key % M;}
int h2(int key){ return 1 + (key%(M - 1)); }

int find(char str[]){
 long long key,h;
 key = getKey(str);
 for(int i = 0; ; i++){
     h = (h1(key) + i * h2(key)) % M;
     if(strcmp(H[h],str) == 0) return 1;
     else if(strlen(H[h]) == 0) return 0;
 }
 return 0;
}

int insert(char str[]){
    long long key,h;
    key = getKey(str);
    for(int i = 0;; i++){
        h = (h1(key) + i * h2(key)) % M;
        if(strcmp(str,H[h]) == 0)return 0;
        else if(strlen(H[h]) == 0){
            strcpy(H[h],str);
            return 0;
        }
    }
    return 0;
}

int main(){
    int i, n, h;
    char str[L], com[9];
    for ( i = 0; i < M; i++ ) H[i][0] = '\0';
    
    scanf("%d", &n);
    
    for ( i = 0; i < n; i++ ){
	scanf("%s %s", com, str);
	
	if ( com[0] == 'i' ){
	    insert(str);
	} else {
	    if (find(str)){
		printf("yes\n");
	    } else {
		printf("no\n");
	    }
	}
    }

    return 0;
}


Measured memory_bytes: 16816
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}
 
ll nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------

int main(void){
    int h, w, a, b;
    cin >> h >> w >> a >> b;

    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(j < a && i < b){
                cout << 1;
            } else if(j < a && i >= b){
                cout << 0;
            } else if(j >= a && i < b){
                cout << 0;
            } else if(j >= a && i >= 0){
                cout << 1;
            }
        }
        cout << endl;
    }
}

Measured memory_bytes: 1280
sa=input()+'a'
sb=input()+'b'
sc=input()+'c'
st='a'
a=0
b=0
c=0
while a<len(sa) and b<len(sb) and c<len(sc):
  if st=='a':
    st=sa[a]
    a+=1
  elif st=='b':
    st=sb[b]
    b+=1
  else:
    st=sc[c]
    c+=1
if a==len(sa):
  print('A')
elif b==len(sb):
  print('B')
else:
  print('C')

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

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

S = input()

diff = 9999
for i in range(len(S)-2):
    s = int(S[i:i+3])
    if abs(s - 753) < diff:
        diff = abs(s - 753)
print(diff)


Measured memory_bytes: 5588
#include <iomanip>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <tuple>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<double> VD;
typedef vector<LL> VLL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef vector<vector<bool>> VVB;
typedef vector<vector<double>> VVD;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(a) (a).begin(),(a).end()

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

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

bool XAND(bool a,bool b){
	if(a and b)return true;
	if(!a and !b)return true;
	return false;
}

int main(){
	string s;cin>>s;
	map<char, int> mp;
	for(char c:s){
		mp[c]++;
	}
	if(XAND(mp['W'],mp['E']) and XAND(mp['N'],mp['S'])){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, As):
    mod = 10 ** 9 + 7
    tmp = sum(As)
    mlt = []
    for i in range(N):
        tmp -= As[i]
        mlt.append(tmp)
    ans = 0
    for i in range(N):
        ans += (As[i] * mlt[i]) % mod
        ans %= mod
    print(ans)


if __name__ == '__main__':
    # S = input()
    N = int(input())
    # N, M = map(int, input().split())
    As = [int(i) for i in input().split()]
    # Bs = [int(i) for i in input().split()]

    # test
    # N = 2 * 10 ** 5
    # As = [10 ** 9 for _ in range(N)]
    solve(N, As)


Measured memory_bytes: 31608
using System;
using System.Collections.Generic;

namespace test
{
    class Program
    {

        static void Main(string[] args)
        {
            List<int> resultList = new List<int>();

            int count = int.Parse(Console.ReadLine());
            for (int i = 0; i < count; i++)
            {
                string[] inputArray = Console.ReadLine().Split(' ');

                decimal xa = decimal.Parse(inputArray[0]);
                decimal ya = decimal.Parse(inputArray[1]);
                decimal ra = decimal.Parse(inputArray[2]);

                decimal xb = decimal.Parse(inputArray[3]);
                decimal yb = decimal.Parse(inputArray[4]);
                decimal rb = decimal.Parse(inputArray[5]);

                decimal d = GetDistance(xa, ya, xb, yb);

                if (d > ra + rb)
                {
                    resultList.Add(0);
                }
                else if (d + rb < ra)
                {
                    resultList.Add(2);
                }
                else if (d + ra < rb)
                {
                    resultList.Add(-2);
                }
                else
                {
                    resultList.Add(1);
                }

            }

            foreach (int a in resultList)
            {
                Console.WriteLine(a);
            }

        }

        static decimal GetDistance(decimal xa, decimal ya, decimal xb, decimal yb)
        {
            decimal x = xa - xb;
            decimal y = ya - yb;

            decimal d = (decimal)Math.Sqrt((double)(x * x + y * y));

            return d;
        }
    }
}

Measured memory_bytes: 5968
#include<stdio.h>
int main(void){
    int T, C=10000, n, c[10000], i, s=0, t[10000];
    scanf("%d%d",&n,&T);
    for(i=0;i<n;i++) scanf("%d%d",&c[i],&t[i]);
    for(i=0;i<n;i++){
        if(t[i]<=T){
            s+=1;
            if(C>c[i]){
                C=c[i];
            }
        }
    }
    if(s==0) printf("TLE\n");
    else printf("%d\n",C);
    return 0;
}

Measured memory_bytes: 128
k, a, b = map(int, input().split())

if b - a <= 2 or k < a -1:
	print(k + 1)
	exit()

res = a
k -= a - 1
if k % 2 == 1:
	res += 1
	k -= 1
res += (b - a) * (k // 2)
print(res)

Measured memory_bytes: 38384
from scipy.sparse.csgraph import floyd_warshall
import numpy as np


N,M = map(int,input().split())
f = lambda x: (int(x[0])-1,int(x[1])-1,int(x[2]))
edges = list(f(input().split()) for _ in range(M))

g = np.zeros((N,N), dtype=float)

for a,b,c in edges:
    g[a,b] = c
    g[b,a] = c

floyd_warshall(g, directed=False, overwrite=True)

res = sum(int(g[a,b] != c) for a,b,c in edges)
print(res)

Measured memory_bytes: 37996
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<bitset>
#include<queue>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
typedef long long ll;
int main(){
	map<int,int> m;
	int n;
	int a;
	int pro = 0;
	cin >> n;
	rep(i,n){
		cin >> a;
		if (a>=3200) pro++;
		else m[a/400]=1;
	}

	int mi,ma;
	int l = m.size();
	if (!pro) mi = l;
	else if (l) mi = l;
	else mi = 1;
	
	ma = (pro) ? (l+pro) : l;

	cout << mi << " " << ma << endl;
	return 0;
}




Measured memory_bytes: 256
n=int(input())
A=input().split()
print(' '.join(A))
for i in range(1,n):
	key=int(A[i])
	j=i-1
	while j>=0 and int(A[j])>key:
		A[j+1]=A[j]
		j-=1
		A[j+1]=str(key)
	print(' '.join(A))




Measured memory_bytes: 5592