akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define ll long long
#define mod 100000007
#define rep(i, n) for (int i = 0; i < n; ++i)
using Graph = vector<vector<int>>;
#define grepq priority_queue<double, std::vector<double>, std::greater<double>>
#define all(v) v.begin(),v.end()
ll INF = 10010001010;

ll lcm(ll a,ll b)
{
    return a * b / __gcd(a, b);
}
typedef tuple<string, int, int> TUP;

bool tuplesort(const TUP &right, const TUP &left)
{
    if (get<0>(right) != get<0>(left))
    {
        return get<0>(left) < get<0>(right);
    }
    if (get<1>(left) != get<1>(right))
    {
        return get<1>(left) > get<1>(right);
    }
    return get<2>(left) < get<2>(right);
}

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

int main(){
    string S;
    cin >> S;
    string s, t = "";
    int ans = 0;
    for (int i = 0; i < S.size();i++)
    {
        s.push_back(S[i]);
        if (s != t)
        {
            t = s;
            ans++;
            s = "";
        }
    }
    cout << ans<< endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define l long long
#define itn int
int b[3005];
int main()
{
	int n;
	itn ans=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&b[i]);
	sort(b,b+n);
	for(int i=0;i<n;i++)
	{
		for(itn c=i+1;c<n;c++)
		{
			int least=c+1;
			int o=lower_bound(b,b+n,b[i]+b[c])-b;
			ans+=o-least;
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

using namespace std;

const int INF = 1000000000;

class Cube{
public:
  string sides[6];
};

int n, i[4], j[4], ans;
Cube data[4];
int next[4][6][4][6];
int d[6][6] = {
  {0, 1, 2, 3, 4, 5},
  {0, 4, 3, 2, 1, 5},
  {0, 2, 4, 1, 3, 5},
  {2, 1, 5, 0, 4, 3},
  {3, 1, 0, 5, 4, 2},
  {0, 3, 1, 4, 2, 5}
};

int comp(){
  if(n == 1) return 0;
  int res = 0;
  for(int i1=0;i1<6;++i1){
    int tmp = INF;
    for(int j1=0;j1<n;j1++){
      int sum = 0;
      for(int k=0;k<n;k++){
	if(j1 == k) continue;
	if(data[j1].sides[next[j1][i[j1]][j[j1]][i1]] != data[k].sides[next[k][i[k]][j[k]][i1]]){
	  sum++;
	}
      }
      tmp = min(tmp, sum);
    }
    res += tmp;
    if(res>=ans) return res;
  }
  return res;
}

main(){
  while(cin >> n && n){
    for(int i1=0;i1<n;i1++){
      for(int j1=0;j1<6;j1++){
	cin >> data[i1].sides[j1];
      }
    }
    for(int l=0;l<4;l++){
      for(int i1=0;i1<6;i1++){
	for(int k=0;k<3;k++){	
	  if(k == 0){
	    for(int j1=0;j1<6;j1++){
	      if(k == 0){
		next[l][i1][k][j1] = d[i1][j1];
	      }
	    }
	  }else{
	    next[l][i1][k][3] = next[l][i1][k-1][3];
	    next[l][i1][k][2] = next[l][i1][k-1][2];
	    next[l][i1][k][5] = next[l][i1][k-1][1];
	    next[l][i1][k][1] = next[l][i1][k-1][0];
	    next[l][i1][k][0] = next[l][i1][k-1][4];
	    next[l][i1][k][4] = next[l][i1][k-1][5];
	  }
	}
      }
    }
    ans = INF;
    for(i[0]=0;i[0]<6;i[0]++){
      for(j[0]=0;j[0]<3;j[0]++){
	if(n>1){
	  for(i[1]=0;i[1]<6;i[1]++){
	    for(j[1]=0;j[1]<3;j[1]++){
	      if(n>2){
		for(i[2]=0;i[2]<6;i[2]++){
		  for(j[2]=0;j[2]<3;j[2]++){
		    if(n>3){
		      for(i[3]=0;i[3]<6;i[3]++){
			for(j[3]=0;j[3]<3;j[3]++){
			  ans = min(ans, comp());
			}
		      }
		    }
		    else ans = min(ans, comp());
		  }
		}
	      }
	      else ans = min(ans, comp());
	    }
	  }
	}
	else ans = min(ans, comp());
      }
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 920
#include <bits/stdc++.h>
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repr(i,a,n) for(int i=a;i>n;i--)
#define leng(n) (int)(log10(n)+1)
#define INF 9000000000000000000
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm

signed main() {
  int n, a, b;
  cin >> n >> a >> b;
  int count = 0;
  int sum = 0;
  int now = 0;
  rep(i,0,n){
    sum = 0;
    now = i+1;
    rep(j,0,leng(i+1)){
      sum += now % 10;
      now /= 10;
    }
    if(sum >= a && sum <= b) count += i+1;
  }
  cout << count << endl;
}


Measured memory_bytes: 256
s = input()[::-1]
words = [w[::-1] for w in ['dream', 'dreamer', 'erase', 'eraser']]

can = 'YES'
while s:
    match_any = False
    for w in words:
        if s.startswith(w):
            s = s.replace(w, '', 1)
            match_any = True
            break
    if not match_any:
        can = 'NO'
        break
print(can)


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (int i = 0; i < sz(v); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << " ";
    }
    return os;
}
int main() {
    int n;
    cin >> n;
    int sn = 0;
    int m = n;
    while (m) sn += m % 10, m /= 10;
    cout << (n % sn ? "No" : "Yes") << endl;
}

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

using namespace std;

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

using ll = long long;

const int Inf = 1e9;
const double EPS = 1e-9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<ll> d;
    rep (i, n) {
        ll a;
        cin >> a;
        if (i == 0) {
            d.push_back(a);
            continue;
        }
        int l = -1, r = d.size(), mid;
        while (abs(r - l) > 1) {
            mid = (l + r) / 2;
            if (d[mid] < a) r = mid;
            else l = mid;
        }
        if (r == d.size()) d.push_back(a);
        else d[r] = a;
    }
    cout << d.size() << endl;
    
    return 0;
}



Measured memory_bytes: 1400
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

// Acknowledgement: Special thanks to kyomukyomupurin, who developed this
// template.
template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
  return os << '(' << p.first << ", " << p.second << ')';
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
  int n = 0;
  for (auto e : vec) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& st) {
  int n = 0;
  for (auto e : st) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::map<T, U>& mp) {
  int n = 0;
  for (auto e : mp) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
  for (T& e : vec) is >> e;
  return is;
}

#ifdef LOCAL
#define debug(...) \
  std::cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out() { std::cerr << '\n'; }

template <class Head, class... Tail>
void debug_out(Head&& head, Tail&&... tail) {
  std::cerr << head;
  if (sizeof...(Tail) != 0) std::cerr << ", ";
  debug_out(std::forward<Tail>(tail)...);
}
using namespace std;
using int64 = long long;

int main() {
  int64 A, B, C, D;
  cin >> A >> B >> C >> D;
  int64 lcm = C * D / __gcd(C, D);
  int64 can_devide_by_C = B / C - (A - 1) / C;
  int64 can_devide_by_D = B / D - (A - 1) / D;
  int64 can_devide_by_CD = B / lcm - (A - 1) / lcm;
  int64 result =
      (B - A + 1) - (can_devide_by_C + can_devide_by_D - can_devide_by_CD);
  cout << result << endl;
  return 0;
}

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

int main(){
  int n, k, r, s, p;
  string t;
  cin >> n >> k >> r >> s >> p >> t;
  int ans=0;
  for(int i=0; i<k; ++i){
    for(int j=0; j<n/k+1; ++j){
      if(j==0){
        if(t.at(k*j+i) == 'r') ans += p;
        if(t.at(k*j+i) == 's') ans += r;
        if(t.at(k*j+i) == 'p') ans += s;
      }
      else if(k*j+i < t.size()){
        if(t.at(k*j+i) == t.at(k*(j-1)+i)){
          t.at(k*j+i) = '0';
        }
        else if(t.at(k*j+i) == 'r') ans += p;
        else if(t.at(k*j+i) == 's') ans += r;
        else if(t.at(k*j+i) == 'p') ans += s;
      }
    }
  }
  cout << ans << endl;
}

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

int main(void) {
  ll n, a, b;
  cin >> n >> a >> b;
  ll x[n];
  rep(i,n) cin >> x[i];
  ll ans=0;
  rep(i,n-1) { //now..x[i],next..x[i+1]
    ll diff=abs(x[i]-x[i+1]);
    ans += min(diff*a,b);
  }
  cout << ans << endl;
}

Measured memory_bytes: 4408
class UnionFind:
    # 負の値はルートで集合の個数
    # 正の値は次の要素を返す
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        while self.table[x] >= 0:
            # 根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    # 併合
    def union(self, x, y):
        s1 = self.find(x)  # 根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        if s1 != s2:  # 根が異なる場合
            if self.table[s1] != self.table[s2]:  # グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                # グラフの長さが同じ場合,どちらを根にしても変わらない
                # その際,グラフが1長くなることを考慮する
                self.table[s1] += -1
                self.table[s2] = s1
        return


def func(n, m, p, x):
    union = UnionFind(n + 1)
    for _x in x:
        union.union(p[_x[0]], p[_x[1]])
    count = 0
    for i in range(n):
        if union.find(i + 1) == union.find(p[i]):
            count += 1
            # print("{}:{}".format(i, union.find(i)))
            # 所属しているunionの根の値を出力する
    # print([union.find(i) for i in range(n+1)])
    return str(count)


n, m = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
x = [[0, 0] for _ in range(m)]
for i in range(m):
    x[i] = [int(i) - 1 for i in input().split()]
print(func(n, m, p, x))
"""
print(str(2) + " vs " + func(5, 2, [5, 3, 1, 4, 2], [[0, 2], [4, 3]]))
print(str(3) + " vs " + func(3, 2, [3, 2, 1], [[0, 1], [1, 2]]))
print(str(8) + " vs " + func(10, 8, [5, 3, 6, 8, 7, 10, 9, 1, 2, 4],
                             [[2, 0], [3, 0], [4, 8], [1, 4], [5, 4], [2, 4], [7, 8], [6, 8]]))
print(str(5) + " vs " + func(5, 1, [1, 2, 3, 4, 5], [[0, 4]]))
# print("print(func({}, {}, {}, {}))".format(n, m, p, x))
"""


Measured memory_bytes: 25956
#include<stdio.h>
#include<string.h>

int balls[13], vis[13], flag;

void dfs(int total, int left, int right)
{
    int i;
    if(total == 11) return; 
    if(flag) return ;
    if(balls[total] > left) dfs(total + 1, balls[total], right);
    else if(balls[total] > right) dfs(total + 1, left, balls[total]);
    else
    {
        flag = 1;
        return;
    }
}

int main()
{
    int T, i, j, k;
    scanf("%d", &T);  //?数

    while(T--)
    {
        flag = 0;
        //??数据中有10个整数
        for(i = 1; i <= 10; i++) scanf("%d", &balls[i]);
        memset(vis, 0, sizeof(vis));
        dfs(1, 0, 0);
        if(flag) printf("NO\n");
        else printf("YES\n");
    }

return 0;
}

/*
?目附?
有一个形似央?大楼（Orz）的筒，从A口可以放球，放?去的球可通??板DE使其掉?B?管或C?管里。
?有?1-10?号的球按?定?序从A口放入，?是否有一?控制?板的策略可以使B?管和C?管中的球从下往上?号??。
?入：
第一行?入数据?数N。接下来N行?N?具体数据，??数据中有10个整数，代表球的放入?序。 
?出：
?于??数据，若策略存在，?出YES；若不存在，?出NO。 
*/

Measured memory_bytes: 580
from itertools import permutations
n = int(input())
f = list(map(int, input().split()))
e = list(map(int, input().split()))
a = sorted(f)
first = 0
end = 0
for i, l in enumerate(permutations(a)):
    if list(l) == f:
        first = i
    if list(l) == e:
        end = i

print(abs(end-first))

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

int main(){
  int n;
  std::cin >> n;
  int max7;
  max7 = int(n/7);
  if(n==4){
    std::cout<< "Yes" << std::endl;
    return 0;
  }
  if(n%7==0){
    std::cout<< "Yes" << std::endl;
    return 0;
  }
  for(int i = 0; i < max7+1; i++){
    if( (n-7*i) % 4 == 0){
      std::cout<< "Yes" << std::endl;
      return 0;
    }
  }
  std::cout<< "No" << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>

using namespace std;
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()

// int DP[MEM_SIZE][MEM_SIZE] = {0};
// int GMEM[MEM_SIZE][MEM_SIZE] = {0};
template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);};
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

//FUNCTION

void solve(void)
{
  int N;
  cin>>N;
  vector<int> vec (N+1,0);
  for (int i = 0; i < N; i++)
  {
    cin>>vec[i+1];
  }
  for (int i = 0; i < N; i++)
  {
    vec[i+1] += vec[i];
  }
  map<int,int> mp;
  for (int i = 0; i < N+1; i++)
  {
    mp[vec[i]]++;
  }
  int ANS = 0;
  for (int i = 0; i < mp.size(); i++)
  {
    static auto itr = mp.begin();
    int X = itr->second;
    ANS +=(X)*(X-1)/2;
    itr++;
  }
  
  cout<<ANS<<endl;
  
  
  
  
  return;
}

int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();

  return 0;
}


Measured memory_bytes: 14336
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
a = [input()[:-1] for _ in range(H)]
dp = [[0]*W for _ in range(H)]
dp[0][0] = 1
MOD = 10**9+7

for i in range(H):
    for j in range(W):
        if a[i][j]=='#':
            continue
        
        if i-1>=0:
            dp[i][j] += dp[i-1][j]
            dp[i][j] %= MOD
        
        if j-1>=0:
            dp[i][j] += dp[i][j-1]
            dp[i][j] %= MOD

print(dp[H-1][W-1])

Measured memory_bytes: 51440
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;
using namespace std;

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

    int maxnum = -100000;

    maxnum = max(maxnum, a + b);
    maxnum = max(maxnum, a - b);
    maxnum = max(maxnum, a * b);

    cout << maxnum << endl;
}

Measured memory_bytes: 256
N, M, C = gets.split.map(&:to_i)
B = gets.split.map(&:to_i)

An = N.times.map do
  gets.split.map(&:to_i)
end

count = 0
An.each do |an|
  sum = C
  an.each_with_index do |a, i|
    sum += a * B[i]
  end

  if sum > 0
    count += 1
  end
end

puts count


Measured memory_bytes: 1788
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int M = Integer.parseInt(sc.next());
        int a, b;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i=0; i<M; i++) {
            a = Integer.parseInt(sc.next());
            b = Integer.parseInt(sc.next());
            if(map.containsKey(a)) map.get(a).add(b);
            else {
                map.put(a, new ArrayList<Integer>());
                map.get(a).add(b);
            }
            if(map.containsKey(b)) map.get(b).add(a);
            else {
                map.put(b, new ArrayList<Integer>());
                map.get(b).add(a);
            }
        }
        
        String ans = "IMPOSSIBLE";
        for(int x : map.get(1)) {
            for(int y : map.get(x)) {
                if(y == N) {
                    ans = "POSSIBLE";
                    break;
                }
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 139672
#include <iostream>

using namespace std;

int main (){
    int r,g,b;
    cin>> r >> g >> b;
    int s;
    s = 100 * r + 10 * g +b;
    if (s%4 == 0)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
//int dp[104][100005];
long long dp[100005];
int main()
{
  long long n,we,i,j;
  cin>>n>>we;
  long long w[n+1],v[n+1];
  for(i=1;i<=n;i++)
  {
    cin>>w[i]>>v[i];
  }
  //2d dp
 /*for(i=1;i<=n;i++)
  {
    for(j=we;j>=w[i];j--)
    {
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
    }
  }
  cout<<dp[n][we];*/
  //1d dp
  for(int i=1;i<=n;i++){
		for(int j=we;j>=w[i];j--){
			dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	long long ans = 0;
	for(int i=0;i<=we;i++) ans=max(ans,dp[i]);
cout<<ans<<endl;
//	cout<<dp[we];
	
	

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define int long long
const int maxn = 100010;
const int inf = 1e18;

inline int read(){
	register int x = 0, g = 1; register char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') g = - 1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') { x = (((x << 2) + x) << 1) + (ch ^ '0'); ch = getchar(); }
	return x * g;
}

static int n, m;
std::vector<int> vec[maxn];

signed main(){
	n = read();
	while(m * (m - 1) / 2 < n) ++m;
	if(m * (m - 1) / 2 > n) return printf("No\n"), 0;
	for(int i = 1, k = 0; i <= m; ++i){
		for(int j = i + 1; j <= m; ++j){
			vec[i].push_back(++k);
			vec[j].push_back(k);
		}
	}
	printf("Yes\n");
	printf("%lld\n", m);
	for(int i = 1; i <= m; ++i){
		printf("%lld ", m - 1);
		for(int j = 0; j < vec[i].size(); ++j)
			printf("%lld ", vec[i][j]);
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 5504
import sys
N,x=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort()
y=x
ans=0
if A[0]>y:
    print(0)
    sys.exit()
for i in range(N):
    if y<A[i]:
        print(ans)
        sys.exit()
    ans+=1
    y-=A[i]
    #print(y)
if y!=0:
    ans-=1
print(ans)

Measured memory_bytes: 38460
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

template <class T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

constexpr int INF = 1 << 30;

bool solve() {
    int n, q;
    std::cin >> n >> q;
    if (n == 0) return false;

    std::vector<std::vector<std::pair<int, int>>> to(n);

    std::vector<int> dist(n);
    MinHeap<std::pair<int, int>> heap;

    while (q--) {
        int t;
        std::cin >> t;

        if (t == 0) {
            int s, g;
            std::cin >> s >> g;
            --s, --g;

            std::fill(dist.begin(), dist.end(), INF);
            dist[s] = 0;
            heap.emplace(0, s);

            while (!heap.empty()) {
                int d, v;
                std::tie(d, v) = heap.top();
                heap.pop();
                if (d > dist[v]) continue;

                for (auto p : to[v]) {
                    int u, c;
                    std::tie(u, c) = p;

                    int nd = d + c;
                    if (nd < dist[u]) {
                        dist[u] = nd;
                        heap.emplace(dist[u], u);
                    }
                }
            }

            std::cout << (dist[g] == INF ? -1 : dist[g]) << "\n";

        } else {
            int u, v, c;
            std::cin >> u >> v >> c;
            --u, --v;
            to[u].emplace_back(v, c);
            to[v].emplace_back(u, c);
        }
    }

    return true;
}

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

    while (solve()) {}

    return 0;
}



Measured memory_bytes: 3068
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        long A = scanner.nextLong();
        long B = scanner.nextLong();
        if ((A+B)%2==0) {
            out.println((A+B)/2);
        }
        else out.println("IMPOSSIBLE");
        out.flush();
    }
    
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
        int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int idx = 0; idx < n; idx++) {
                a[idx] = nextInt();
            }
            return a;
        }
    }
}


Measured memory_bytes: 21204
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#define rep(i,n) for(int i=0;i<(n);i++)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define All(x) (x).begin(),(x).end()
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
int BinarySearch(int key,int n,int S[]){
  int l=0,r=n;
  while(r-l>1){
    int mid=(l+r)/2;
    if(S[mid]>key)r=mid;
    else l=mid;
  }
  return S[l]==(key?1:0);
}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8


int main() {
    char S[100007];cin>>S;
    for(int i=0;i<strlen(S);i+=2){
        cout <<S[i];
    }
    cout <<  endl;
}

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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
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; }
typedef long long ll;

const long long INF = 1LL << 60;

int main()
{
    int N, K;
    cin >> N >> K;

    ll cnt1 = 0, cnt2 = 0;
    repd(i, 1, N + 1) {
        if (i % K == 0) cnt1++;
        else if (i % K == (float)K / 2.0) cnt2++;
    }

    ll ans =  pow(cnt1, 3LL) + pow(cnt2, 3LL);

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

Measured memory_bytes: 256
def actual(N, S):
    count = 0

    for i in range(1, N):
        left_chars = set(S[:i])
        right_chars = set(S[i:])

        and_chars = left_chars & right_chars
        unique_chars = len(and_chars)

        if unique_chars > count:
            count = unique_chars

    return count

N = int(input())
S = input()

print(actual(N, S))

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

int main() {
  int a;
  cin>>a;
  string b,c;
  cin>>b>>c;
  reverse(b.begin(),b.end());
  string d,e;
  int answer;
  for(int i=0;i<=a;i++){
    for(int j=0;j<i;j++){
      d+=b.at(j);
    }
    for(int j=0;j<i;j++){
      e+=c.at(j);
    }
    reverse(d.begin(),d.end());
    if(d==e){
      answer=i;
    }
    d="";
    e="";
  }
  cout<<a*2-answer<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;

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

    string s;
    cin >> s;
    int n = s.size();

    int res = 0;
    for(int i = 0; i < n; ++i){
        for(int j = i; j < n; ++j){
            string sub = s.substr(i, j-i+1);
            bool flg = true;
            rep(k, sub.size()){
                char c = sub[k];
                if(c=='A' || c=='C' || c=='G' || c=='T') flg = flg && true;
                else flg = false;
            }

            if(flg) res = max(res, (int)sub.size());
        }
    }

    cout << res << endl;


    return 0;
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
flg=True
for i in range(n):
    t=a[i]
    if t%2==0:
        if t%3!=0 and t%5!=0:
            flg=False
if flg:
    print("APPROVED")
else:
    print("DENIED")

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


int main(){
  int a,b,c;
  cin >> a >> b >> c;
  int ma=max(a,b);
  ma=max(ma,c);
  int saa=ma-a;
  int sab=ma-b;
  int sac=ma-c;
  int ans=0;
  if(saa==0){
    if(sab%2==0 && sac%2==0){
      ans=sab/2+sac/2;
    }else if(sab%2==1 && sac%2==1){
      ans=min(sab,sac)+abs(sab-sac)/2;
    }else{
      if(sab%2==0 && sac%2==1){
        ans=sab/2+(sac+1)/2;
        ans++;
      }else{
        ans=(sab+1)/2+sac/2;
        ans++;
      }
    }
  }else if(sab==0){
    if(saa%2==0 && sac%2==0){
      ans=saa/2+sac/2;
    }else if(saa%2==1 && sac%2==1){
      ans=min(saa,sac)+abs(saa-sac)/2;
    }else{
      if(saa%2==0 && sac%2==1){
        ans=saa/2+(sac+1)/2;
        ans++;
      }else{
        ans=(saa+1)/2+sac/2;
        ans++;
      }
    }
  }else{
    if(sab%2==0 && saa%2==0){
      ans=sab/2+saa/2;
    }else if(sab%2==1 && saa%2==1){
      ans=min(sab,saa)+abs(sab-saa)/2;
    }else{
      if(sab%2==0 && saa%2==1){
        ans=sab/2+(saa+1)/2;
        ans++;
      }else{
        ans=(sab+1)/2+saa/2;
        ans++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
	string s;
	cin >> s;

	bool ans = false;
	sort(s.begin(), s.end());
	if(s.at(0) == s.at(1) && s.at(2) == s.at(3) && s.at(0) != s.at(2))
		cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    static int MOD = 1000000007;
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        String[][] table = new String[x + 2][y + 2];
        for (String[] t : table) {
            Arrays.fill(t, "#");
        }
        for (int i = 1; i <= x; i++) {
            String str = sc.next();
            for (int j = 1; j <= y; j++) {
                table[i][j] = String.valueOf(str.charAt(j - 1));
            }
        }
        
        int[][] dp = new int[x + 2][y + 2];
        dp[1][1] = 1;
      
        for (int i = 1; i <= x; i++) {
            for (int j = 1; j <= y; j++) {
                if (table[i][j].equals("#")) continue;
                
                boolean upToDown = table[i - 1][j].equals(".");
                boolean leftToRight = table[i][j - 1].equals(".");
                
                if (upToDown && leftToRight) {
                    dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
                } else if (upToDown) {
                    dp[i][j] = dp[i - 1][j];
                } else if (leftToRight) {
                    dp[i][j] = dp[i][j - 1];
                } else {
                    if (i == 1 && j == 1) continue;
                    table[i][j] = "#";
                    if (i == x && j == y) {
                        dp[i][j] = 0;
                    }
                }
            }
        }
        
        System.out.println(dp[x][y]);
    }
}

Measured memory_bytes: 83480
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

ll n,m,ans,cnt;
bool b[52][52],ch[52];
ll l[52],r[52];
void dep(ll now){
	if(cnt==n){
		ans++;
		return ;
	}
	for(ll i=0;i<n;i++){
		if(b[now][i]==false){
			continue;
		}
		if(ch[i]==true){
			continue;
		}
		ch[i]=true;
		cnt++;
		dep(i);
	}
}
int main() {
	cin>>n>>m;
	for(ll i=0;i<m;i++){
		ll x,y;
		cin>>x>>y;
		x--;y--;
		l[i]=x,r[i]=y;
		b[x][y]=b[y][x]=true;
	}
	for(ll i=0;i<m;i++){
		for(ll j=0;j<n;j++){
			ch[j]=false;
		}
		ll nowl=l[i],nowr=r[i];
		b[nowl][nowr]=b[nowr][nowl]=false;
		ch[0]=true;cnt++;
		dep(0);
		b[nowl][nowr]=b[nowr][nowl]=true;
		cnt=0;
	}
	cout << m-ans;
	// your code goes here
	return 0;
}

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

template<typename T, typename U>
using pv=vector<pair<T,U>>;
template<typename T>
using matrix=vector<vector<T>>;
template<typename T>
using pque=priority_queue<T>;
template<typename T>
using lpque=priority_queue<T,vector<T>,greater<T>>;

using ll=long long;
using intpair=pair<int,int>;
using llpair=pair<ll,ll>;
using ilpair=pair<int,ll>;
using lipair=pair<ll,int>;
using intvec=vector<int>;
using llvec=vector<ll>;
using intq=queue<int>;
using llq=queue<ll>;
using intmat=vector<intvec>;
using llmat=vector<llvec>;

#define PI 3.141592653589793
#define INTINF ((1<<30)-1)
#define LLINF ((1LL<<62)-1)
#define MPRIME 1000000007
#define MPRIME9 998244353
#define MMPRIME ((1ll<<61)-1)

#define len length()
#define pushb push_back
#define fi first
#define se second

#define setpr fixed<<setprecision(15)
#define all(name) name.begin(),name.end()
#define rall(name) name.rbegin(),name.rend()
#define gsort(vbeg,vend) sort(vbeg,vend,greater<>())

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;
}

template<class T>
inline void init(T& v) {
	for(auto &a: v) cin>>a;
}
template<class T, class U>
inline void init(vector<pair<T,U>>& v) {
	for(auto &a: v) cin>>a.first>>a.second;
}
template<class T, class N>
inline void init(T& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a;
}
template<class T, class U, class N>
inline void init(vector<pair<T,U>>& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a.first>>a.second;
}

inline void out() {
	cout<<endl;
}
template<class T, class... U>
inline void out(T a, U... alist) {
	cout<<a<<" ";
	out(forward<U>(alist)...);
}

template<class N>
void resiz(N n) {
	//empty
}
template<class N, class T, class... U>
void resiz(N n, T&& hd, U&&... tl) {
	hd.resize(n);
	resiz(n,forward<U>(tl)...);
}

bool isout(int h, int w, int H, int W) {
	return ( h<0 || h>=H || w<0 || w>=W );
}

ll binpow(ll a, ll ex, ll p) {
	ll result=1;
	while(ex>0) {
		if(ex&1) result=result*a%p;
		ex>>=1;
		a=a*a%p;
	}
	return result;
}


int N,K;
intvec P;
llvec C;
pv<ll,int> rch;
ll ans=-LLINF;

void input() {
	cin>>N>>K;
	P.resize(N); for(int i=0; i<N; i++) { cin>>P[i]; P[i]--; }
	init(C,N);
	rch.resize(N);
}

void solve() {
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) rch[j]={-LLINF,-1};
		rch[i]={0,0};
		int now=i;
		ll score=0;
		for(int j=K-1; j>=0; j--) {
			now=P[now];
			score+=C[now];
			chmax(ans,score);
			if(rch[now].se<0) rch[now]={score,K-j};
			else {
				int rnum=K-j-rch[now].se;
				ll rsc=score-rch[now].fi;
				if(rsc<0) break;

				if(j/rnum>0) {
					score += rsc*(j/rnum-1);
					j%=rnum; j+=rnum;
				}
				chmax(ans,score);

				for(int k=0; k<j; k++) {
					now=P[now];
					score+=C[now];
					chmax(ans,score);
				}
				break;
			}
		}
	}
	cout<<ans<<endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout<<fixed<<setprecision(15);
	int t=1;
	while(t) {
		input();
		solve();
		t--;
	}
}


Measured memory_bytes: 3776
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);



int main(){
  string s;
  cin >> s;
  s[3] = '8';

  cout << s << endl; 
  return 0;
}


Measured memory_bytes: 3628
#include <iostream>

using namespace std;

int main()
{
	int n,d[55];
    int ans=0;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> d[i];
	for (int i = 0; i < n; i++) {
		for (int k = 0; k < n; k++) {
			if (k <= i)  continue;
			else
				ans += d[i] * d[k];
		}
	}
	cout << ans << endl;
	return 0;
}

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

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

    int mul = a*b;
    int sum = a+b;
    int diffrence = a-b;

    if(mul > sum && mul > diffrence)
        cout << mul;
    else if (sum > mul && sum > diffrence)
        cout << sum;
    else if (diffrence > mul && diffrence > sum)
        cout << diffrence;
    else
        cout << sum;
    return 0;
}


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

int main(){
	int N,M;
	cin >> N >> M;
	vector<pair<ll,int>> A(N);
	rep(i,N){
		ll a;
		cin >> a;
		A[i] = make_pair(a,1);
	}
	
	vector<pair<ll,int>> B(M);
	rep(i,M){
		int x;
		ll y;
		cin >> x >> y;
		B[i] = make_pair(y,x);
	}
	
	B.insert(B.end(), A.begin(), A.end());
	sort(B.begin(), B.end());
	reverse(B.begin(),B.end());
	
	ll ans = 0;
	
	
	int count = 0;
	
	rep(i,N){
		rep(j,B[i].second){
			ans += B[i].first;
			count++;
			if(count == N){
				break;
			}
		}
		if (count == N){
			break;
		}
	}
	
	
	cout << ans << endl;
	
}



Measured memory_bytes: 6528
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;

int main(){
    int n;
    string s;

    cin >> n >> s;

    int e[300000]={};
    int w[300000]={};

    for(int i=0;i<n-1;i++){
        w[i+1]=w[i];
        if(s[i]=='W'){
            w[i+1]++;
        }
    }
    for(int i=n-1;i>0;i--){
        e[i-1]=e[i];
        if(s[i]=='E'){
            e[i-1]++;
        }
    }
    int min = n;
    int min_i = 0;
    for(int i=0;i<n;i++){
        if(min > e[i] + w[i]){
            min = e[i] + w[i];
            min_i = i;
        }
    }

    cout << min << endl;


    return 0;
}

Measured memory_bytes: 3076
def main():
    N = int(input())
    T = list(map(int, input().split()))
    M = int(input())
    P, X = [0] * M, [0] * M
    for i in range(M):
        P[i], X[i] = map(int, input().split())
    s = sum(T)
    for i in range(M):
        print(s - T[P[i]-1] + X[i])

if __name__ == '__main__':
    main()


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


int main(){
    int n;
    int he[100005],dp[100005];
    cin >> n;
    
    for(int i=1;i<=n;i++){
        cin >> he[i];
    }
    
    for(int i=n;i>=0;i--){
        if(i==n) dp[i]=0;
        else if(i+1==n) dp[i]=abs(he[i]-he[i+1])+dp[i+1];
        else{
           int t1,t2;
        t1=abs(he[i]-he[i+1])+dp[i+1];
        t2=abs(he[i]-he[i+2])+dp[i+2]; 
        dp[i]=min(t1,t2);
        }
    }
    cout << dp[1] << endl;
    
}

Measured memory_bytes: 4424
#include <stdio.h>

int main(void){

    int a, b, c;

    scanf("%d%d%d",&a,&b,&c);

    if(a==b && a != c){
        printf("Yes");
        return 0;
    }else if(a==c && a != b){
        printf("Yes");
        return 0;
    }else if(c==b && c != a){
        printf("Yes");
        return 0;
    }

    printf("No");

    return 0;
}

Measured memory_bytes: 1728
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    print(k*((k-1)**(n-1)))

if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
/**
 *      ///----- My Info -----///
 *      Code by: Unk
 *      Codeforces User: Ernest0_0Abreu
 *      Country: Cuba
 *      E-mail: ernestoabreup@gmail.com
 *      CopyRight
**/
#include <bits/stdc++.h>
#ifdef Ernest0_0Abreu 
#include <debug/to_string.h>
#endif
#pragma GCC optimize("Ofast")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
        ///----- My Template -----///
///===================================================================================================================================
/// Debug
#define _end cout << "\n"
#ifndef Ernest0_0Abreu
#define db(x) ;
#define dbrange(x,begin,end) ;
#define dbname(x) ;
#define dbnamerange(x,begin,end) ;
#define dbmat(x,begin_n,end_n,begin_m,end_m) ;
#define dbST(x,end) ;
#define db_end ;
#endif
///Function
#define pi (acos(-1))
#define lg2(x) ( 31-__builtin_clz(x) )
#define lgx(x,n) ( log(n) / log(x) )
/// Macros
#define fst first
#define scd second
#define left (node<<1)
#define right ((node<<1)+1)
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
/// Typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
/// Constant
const int MAXN = 1e6+7;
const int MOD = 1e9+17;
const ull BASE = 311;
const ld EPS = 1e-9;
const int INF = ((1<<30)-1);
const ll INFLL = ((1ll<<62ll)-1ll);
const ll oo = 2e18;
/// Hash Prime Numbers: 2, 277, 293, 307, 331, 337, 1009, 2027, 3079, 10079;
/// Module Prime Numbers: 3, 200017, 1000033, 998244353, 1000000007, 1000000009, 1000000021;
#define int long long
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
///===================================================================================================================================
        ///----- My code -----///



int32_t main(){
    
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

 	int K;
 	cin >> K;
 	string s;
 	cin >> s;
 	if(sz(s) <= K) cout << s;
 	else {for(int i = 0; i < K; ++i) cout << s[i]; cout << "...";}
    return 0;
}


Measured memory_bytes: 3640
while True:
    try:
        for i in range(3):
            line = raw_input().strip()
            if line == '0':
                raise Exception

            a = b = 0
            for i, s in enumerate(line):
                if i != 0:
                    if s == 'A':
                        a += 1
                    else:
                        b += 1
            if a > b:
                a += 1
            else:
                b += 1
            print a, b

    except:
        break

Measured memory_bytes: 4228
#include "bits/stdc++.h"
using namespace std;
 
#define ll                          long long
 
#define forn(i,n)                   for(int i=0;i<n;i++)
#define all(v)                      v.begin(), v.end()
#define rall(v)                     v.rbegin(),v.rend()
	
#define pb                          push_back
#define sz(a)                       (int)a.size()
 
#define   endl                       "\n"
#define fastio                       ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
const int mod = 1e9 + 7;
int32_t  main()
{
	int n;
	cin >> n;
	int a[n];
	int s = 0;
	forn(i,n){
		cin>>a[i];
		s += a[i];
	}
	int suffixsum[n];
	int k =  0;
	for(int i = 0;i < n;i++)
	{
		k+= a[i];
		suffixsum[i] = (s - k) % mod;
	}
	int ans = 0;
	for(int i = 0;i < n - 1 ;i++)
	{
		int add = (a[i] * suffixsum[i]) % mod;
		ans = (ans + add) % mod;
	}
	cout<<ans;
}

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

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

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

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

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

#define en "\n"

const double EPS = 1e-9;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0, sizeof(a))

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

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

int ans,H,a[10][5];

bool check(void){
    bool res = false;
    REP(i,H){
        RFOR(j,6,3){
            REP(k,5-j+1){
                bool flag = true;
                REP(l,j-1){
                    if(a[i][k]==0 || a[i][k+l+1]==0){
                        flag = false;
                        break;
                    }
                    if(a[i][k+l+1] != a[i][k]){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    res = true;
                    ans += a[i][k]*j;
                    REP(l,j) a[i][k+l] = 0;
                }
            }
        }
    }
    return res;
}

void seiri(void){
    RREP(i,H){
        REP(j,5){
            if(a[i][j] == 0){
                int h = i-1;
                while(h>0 && a[h][j]==0) h--;
                if(h>=0 && a[h][j] != 0){
                    a[i][j] = a[h][j];
                    a[h][j] = 0;
                }
            }
        }
    }
}

int main(void){
    cin >> H;
    while(H != 0){
        ans = 0;
        REP(i,H)REP(j,5) cin >> a[i][j];
        while(check()) seiri();
        cout << ans << en;
        cin >> H;
    }
    return 0;
}


Measured memory_bytes: 3092
import bisect

n = int(input())
arr = [int(input()) for _ in range(n)]
colors = []

colors.append(arr[-1])
cnum = len(colors)
for a in arr[-2::-1]:
  i = bisect.bisect_right(colors, a)
  if i < cnum:
    colors[i] = a
  else:
    colors.append(a)
    cnum += 1

print(cnum)



Measured memory_bytes: 8604
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
#define TO(x,t,f) ((x)?(t):(f))
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define FILV(x,a) fill(x.begin(),x.end(),a)
#define FILA(ar,N,a) fill(ar,ar+N,a)
#define NEXTP(x) next_permutation(x.begin(),x.end())
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define pb push_back
#define pri(aa) cout<<(aa)<<endl
const ll INF=1e9+7;
const ll N = 100002;
set<string> s;
ll n;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	FOR(i,0,n){
		string p,k;
		cin>>p>>k;
		if(p=="insert")s.insert(k);
		else {
			if(s.count(k)==1)pri("yes");
			else pri("no");
		}
	}
	return 0;
}


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

int main() {
    int a, b;

    cin >> a >> b;

    int ans = 0;

    if (a > b) {
        ans += a;
        a--;
    } else {
        ans += b;
        b--;
    }

    if (a > b) {
        ans += a;
        a--;
    } else {
        ans += b;
        b--;
    }

    cout << ans << endl;

    return 0;
}


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

int main(void){
    int n, m, sw[10];
    
    cin >> n >> m;
    for (int i=0;i<m;i++) {
        int k;
        bitset<10> s;
        cin >> k;
        for (int j=0;j<k;j++) {
            int sw_tmp;
            cin >> sw_tmp;
            s.set(sw_tmp - 1);
        }
        sw[i] = s.to_ulong();
    }
    int p[20];
    for (int i=0;i<m;i++) {
        cin >> p[i];
    }
    
    // bit全探索
    // (1<<n) = 2^n
    // 今回はmax10なので1024回るーぷ
    int ans=0;
    for (int bit = 0; bit < (1<<n); ++bit) {
        vector<int> vec;
        
        for (int i = 0; i < n; ++i) {
            // bit に i番目のフラグが立っている
            if (bit & (1<<i)) { 
                vec.push_back(i);
            }
        }
        
        // 電球m回(max 10)ループ
        bool flag = true;
        for (int light=0; light<m; light++) {
            // cout << "flag " << flag << endl;
            // cout << endl;
            // cout << "bit " << bit << endl;
            // cout << "light " << light << endl;
            int count = 0;
            for (int i = 0; i < (int)vec.size(); ++i) {
                // onの時
                if(sw[light] & (1<<vec[i])) {
                    count++;
                }
            }
            // cout << "count " << count << endl;
            // cout << "p " << p[light] << endl;
            if(count % 2 != p[light]) {
                flag = false;
                continue;
            }
        }
        if(flag) {
            ans++;
        }
    }
    
    // for (int i=0;i<m;i++) {
    //     cout << s[i] << endl;
    // }
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
n = gets.to_i
s = gets.chomp.split.map(&:to_i)
q = gets.to_i
t = gets.chomp.split.map(&:to_i)
cnt = 0

def binary_search(arr, key)
  ng = -1
  ok = arr.size

  while (ok - ng).abs > 1
    mid = (ok + ng) / 2
    if arr[mid] >= key
      ok = mid
    else
      ng = mid
    end
  end
  arr[ok]
end

t.each do |i|
  cnt += 1 if binary_search(s,i) == i
end

puts cnt



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

int main (){
int x = 0,a = 0,b = 0;
cin >> x ;
a = x / 500;
x = x % 500;
b = x / 5;

cout << a * 1000 + b * 5 << endl;
return 0;

}


Measured memory_bytes: 3612