akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
#define N 200
#define M 10000
#define R 1000
#define INF 1000000

int main(){
  while(1){
    int n,m,r;
    int sea[N][N];
    int land[N][N];
    int dp[R][N];
    int z[R];

    scanf("%d%d",&n,&m);
    if(!n&&!m)break;

    //陸路と海路を別々に全点対最短路を求める
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        if(i==j){
          sea[i][j] = 0;
          land[i][j] = 0;
        }else{
          sea[i][j] = INF;
          land[i][j] = INF;
        }
      }
    }
    for(int i=0;i<m;i++){
      int x,y,t;
      char s;
      scanf("%d %d %d %c",&x,&y,&t,&s);
      if(s=='S'){
        sea[x-1][y-1] = t;
        sea[y-1][x-1] = t;
      }else{
        land[x-1][y-1] = t;
        land[y-1][x-1] = t;
      }
    }
    for(int k=0;k<n;k++){
      for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
          sea[i][j] = min(sea[i][j],sea[i][k]+sea[k][j]);
          land[i][j] = min(land[i][j],land[i][k]+land[k][j]);
        }
      }
    }

    scanf("%d",&r);
    for(int i=0;i<r;i++){
      scanf("%d",&z[i]);
      z[i]--;
    }

    //dp[i][j]をjに船をおいてz[i]まで進んだ時にかかる最短の時間
    for(int i=0;i<n;i++){
      dp[0][i] = sea[z[0]][i] + land[i][z[0]];
      for(int j=1;j<r;j++){
        dp[j][i] = INF;
      }
    }
    for(int i=1;i<r;i++){
      for(int j=0;j<n;j++){
        for(int k=0;k<n;k++){
          dp[i][j] = min(
            dp[i][j],
            dp[i-1][k]+land[z[i-1]][k]+sea[k][j]+land[j][z[i]] );
          if(k==j) dp[i][j] = min(dp[i][j],dp[i-1][j]+land[z[i-1]][z[i]]);
        }
      }
    }

    int ans = INF;
    for(int i=0;i<n;i++){
      ans = min(ans,dp[r-1][i]);
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 2304
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <cstring>
using namespace std;
typedef long long int ll;
const int INF = 1000000000;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
int main(){
    string s;
    while(getline(cin, s)){
        rep(i, 26){
            for(char& c : s){
                if(isalpha(c)){
                    if(c != 'z') ++c;else c = 'a';
                }
            }
            if(s.find("that") != string::npos || s.find("this") != string::npos || s.find("the") != string::npos){
                cout << s << endl;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3056
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define IFOR(i,a,b) for(int i=(b-1);i>=(a);--i)
#define RPT(i,a,b) for(int i=(a);i<((a)+(b));++i)
#define IRPT(i,a,b) for(int i=((a)+(b)-1);i>=(a);--i)

template<typename T>
using V = vector<T>;

template<typename T>
using V2 = V<V<T>>;

template<typename T>
using V3 = V<V2<T>>;

constexpr int search_ = 15000;

void solve(){
  int search = search_;
  int h, w;
  cin >> h >> w;
  V2<int> a(h, V<int>(w)), b(h, V<int>(w));
  FOR(i,0,h) FOR(j,0,w) cin >> a[i][j];
  FOR(i,0,h) FOR(j,0,w) cin >> b[i][j];
  V3<int> dp(h+1, V2<int>(w+1, V<int>(2*search+10,0) ) );
  //FOR(i,0,h+1) FOR(j,0,w+1) FOR(k,0,2*search+5) dp[i][j][k]=0;
  dp[0][1][0] = 1;
  FOR(i,0,h){
    FOR(j,0,w){
      int df = abs(a[i][j] - b[i][j]);
      FOR(k,0,2*search){
        if( abs(k+df) >= 0 && abs(k+df) <= 2*search )dp[i+1][j+1][abs(k+df)] += ((dp[i][j+1][k]+dp[i+1][j][k])>0);
        if(abs(k-df) >= 0 && abs(k-df) <= 2*search )dp[i+1][j+1][abs(k-df)] += ((dp[i][j+1][k]+dp[i+1][j][k])>0);
      }
    }
  }
  int ans = 987654321;
  FOR(i,0,2*search){
    if(dp[h][w][i]){
      ans = min(ans, i);
    }
  }
  cout << ans << endl;
}

int main(void){
  solve();
  return 0;
}

Measured memory_bytes: 781312
#include <bits/stdc++.h>
#define maxn 4086 
typedef long long ll;
using namespace std;
const ll mod = 1e9 + 7;

inline ll read(){
	ll x = 0, f = 1;char ch = getchar();
	while(ch > '9' || ch < '0'){if(ch == '-') f = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = x * 10 + ch -'0';ch = getchar();}
	return x * f;
}
int t, n;
priority_queue<ll> Q1,Q3;
priority_queue<ll,vector<ll>,greater<ll> >Q2,Q4;
int main(){
	int x, y;
	n = read();
	int i;
	for(i = 1;i <= n;i++) {
		x = read(), y = read(),Q1.push(x - y),Q2.push(x - y);
		Q3.push(x + y), Q4.push(x  +y );
	}
	printf("%lld\n",max(Q1.top() - Q2.top(), Q3.top() - Q4.top()));
}

Measured memory_bytes: 9676
#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; }
// 多次元 vector 生成
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...));
}

const int MOD = 1000000007;

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;
    }
    bool operator==(const mint a){
        return (x == a.x);
    }
    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 n, k; cin >> n >> k;
    k = min(k, n-1);
    combination c(n);
    mint ans = 0;
    for (int i = 0; i <=k; i++){
        ans += c(n,i) * c((n-i-1)+i, i);
    }

    cout << ans << endl;

}

Measured memory_bytes: 6336
#include <stdio.h>
#include <string.h>
int main()
{

    char a[102],b[102],c[102];
    int s,d,f,g,h,j,k,len;
    scanf("%s%s%s",a,b,c);
len=strlen(a);
    for(s=0;s<len;s++){
        if(s==len-1) {
            d= a[s];
        }
    }
    len=strlen(b);
    for(j=0;j<len;j++) {
        if (j ==0) {
            f = b[j];
        }
    }
    len=strlen(b);
    for(j=0;j<len;j++) {
        if (j==len-1) {
            g= b[j];
        }}
    len=strlen(c);
    for(k=0;k<len;k++) {
        if (k ==0) {
            h=c[k];
        }}
    if(d==f&&g==h){
        printf("YES");
    } else{
        printf("NO");
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 128
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
a = set(a)
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
        if i in a:
                continue
        if i == 1:
                dp[i] = 1
                continue
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod
print(dp[n]%mod)

Measured memory_bytes: 13552
import java.util.Scanner;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int max = -1000;

        sc.close();

        if(a+b > max) max = a+b;
        if(a-b > max) max = a-b;
        if(a*b > max) max = a*b;

        System.out.println(max);

    }
}

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

using namespace std;

#define INF (1 << 30)
#define EPS 1e-10
#define MOD 1000000007

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

using ll = long long;

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

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

int b[1000001];

int main() {
    int n, a, s;
    bool p = true;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        if (a > 1 && p) {
            for (int i = 1; i * i <= a; ++i) {
                if (a % i == 0) {
                    if ((i > 1 && b[i]) || b[a / i])
                        p = false;
                    b[i] = 1;
                    b[a / i] = 1;
                }
            }
        }

        if (i == 0)
            s = a;
        else
            s = gcd(s, a);
    }
    if (p)
        cout << "pairwise coprime" << endl;
    else if (s == 1)
        cout << "setwise coprime" << endl;
    else
        cout << "not coprime" << endl;

    return 0;
}

Measured memory_bytes: 7496
N = int(input())
S = input()
if N == 1:
  print("No")
  exit()
rep_cnt = N / 2
s1 = []
s2 = []
for i, s in enumerate(S):
  if i < rep_cnt:
    s1.append(s)
  else:
    s2.append(s)
if s1 == s2:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
set<pii> s;
vi v;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=0; i<(1<<n); i++)
    {
        int szam;
        cin>>szam;
        s.insert({szam, i+1});
    }
    auto it=s.end();
    it--;
    v.push_back(it->first);
    s.erase(it);
    for(int kor=0; kor<n; kor++)
    {
        for(int i=0; i<(1<<kor); i++)
        {
            it=s.lower_bound({v[i], 0});
            if(it==s.begin())
            {
                cout<<"No"<<endl;
                return 0;
            }
            it--;
            v.push_back(it->first);
            s.erase(it);
        }
    }
    cout<<"Yes"<<endl;


    return 0;
}


Measured memory_bytes: 13688
#include<bits/stdc++.h>
using namespace std;
signed main(){
  int n;
  cin>>n;
  int A[n];
  for(int i=0;i<n;i++) cin>>A[i];
  for(int k=0;k<n;k++) cout<<A[k]<<" \n"[k==n-1];
  for(int i=1;i<n;i++){
    int v=A[i];
    int j=i-1;
    while(j>=0&&A[j]>v){
      A[j+1]=A[j];
      j--;
    }
    A[j+1]=v;
    for(int k=0;k<n;k++) cout<<A[k]<<" \n"[k==n-1];
  }
  return 0;
}

Measured memory_bytes: 3068
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
#include <deque>
#include <complex>
#include <bitset>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<long long, long long> pll;
typedef vector<pll> vpll;

typedef long double ld;
typedef vector<ld> vld;

typedef vector<bool> vb;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, n) for (ll i = 1; i <= (n); i++)
#define rrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rreps(i, n) for (ll i = (n); i >= 1; i--)
#define all(v) (v).begin(), (v).end()

template <class T> void chmin(T& a, T b) { a = min(a, b);}
template <class T> void chmax(T& a, T b) { a = max(a, b);}

constexpr int INF = 1 << 30;
constexpr ll INFL = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-12;
ld PI = acos(-1.0);

void solve() {
    ll n;
    cin >> n;
    vector<multiset<ll>> vs(1 << n);
    for(int i = 0; i < (1 << n); ++i) {
        ll a;
        cin >> a;
        vs[i].insert(a);
    }
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < (1 << n); ++j) {
            if(!(j & (1 << i))) continue;
            multiset<ll>& _vs = vs[j ^ (1 << i)];
            for(auto it = _vs.begin(); it != _vs.end(); ++it) vs[j].insert(*it);
            while(vs[j].size() > 2) vs[j].erase(vs[j].begin());
        }
    }
    ll last_ans = 0;
    for(int i = 1; i < (1 << n); ++i) {
        ll ans = *vs[i].begin() + *vs[i].rbegin();
        chmax(ans, last_ans);
        cout << ans << endl;
        last_ans = ans;
    }
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}

Measured memory_bytes: 40264
import math
n,h = map(int, input().split())
a, b = [], []
for _ in range(n):
    c,d = map(int, input().split())
    a.append(c)
    b.append(d)
mx = max(a)
ups = [x for x in b if mx < x]
if sum(ups) >= h:
    tmp = 0
    cnt = 0
    for up in sorted(ups)[::-1]:
        tmp += up
        cnt += 1
        if tmp >= h:
            print(cnt)
            exit()
h -= sum(ups)
ans = len(ups) + math.ceil(h / mx)
print(ans)

Measured memory_bytes: 13312
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(n) for (ll i = 0; i < n; ++i)
#define rep2(i, n) for (ll i = 0; i < n; ++i)
#define rep3(i, a, b) for (ll i = a; i < b; ++i)
#define rep4(i, a, b, c) for (ll i = a; i < b; i += c)
#define erep(n) for (ll i = 0; i <= n; ++i)
#define erep2(i, n) for (ll i = 0; i <= n; ++i)
#define erep3(i, a, b) for (ll i = a; i <= b; ++i)
#define erep4(i, a, b, c) for (ll i = a; i <= b; i += c)
#define rrep(i, a, b) for (ll i = a; i > b; --i)
#define rrep2(i, a, b, c) for (ll i = a; i > b; i -= c)
#define errep(i, a, b) for (ll i = a; i >= b; --i)
#define errep2(i, a, b, c) for (ll i = a; i >= b; i -= c)
#define print(a) cout << a << endl;
#define printVec(v) printf("{"); for (const auto& i : v) { std::cout << i << ", "; } printf("}\n");
#define cin(x) cin >> x;
const ll MOD = 1000000007;
const double PI = 3.14159265358979323846264338327950;
inline int newline() { putchar('\n'); return 0; }

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

    vector<ll> a(n), b(m);
    rep2(i, n) cin(a[i]);
    rep2(i, m) cin(b[i]);

    vector<ll> as(n + 1, 0), bs(m + 1, 0);
    rep3(i, 1, n + 1) as[i] = as[i - 1] + a[i - 1];
    rep3(i, 1, m + 1) bs[i] = bs[i - 1] + b[i - 1];

    ll result = 0;
    rep2(i, n + 1) {
        ll left = k - as[i];

        if (left < 0) break;

        vector<ll>::iterator position = upper_bound(bs.begin(), bs.end(), left);
        ll index = distance(bs.begin(), position);

        result = max(result, i + index - 1);
    }

    print(result);
    return 0;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
const long long INF = 1LL << 60;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int A,B,C;
  ll N;
  cin >> A >> B >> C;
  cin >> N;
  if(N%2==1)
  {
    cout << B - A << endl;
  }
  else
  {
    cout << A - B << endl;
  }
  return 0;
}


Measured memory_bytes: 3604
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
template<class T, class Compare = less<T> >
using MaxHeap = priority_queue<T, vector<T>, Compare>;
template<class T, class Compare = greater<T> >
using MinHeap = priority_queue<T, vector<T>, Compare>;
using llong = long long;

int main() {
    llong ans = 0;
    llong n;
    string s;

    cin >> s;

    n = s.length();

    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - i - 1]) ans++;
    }

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int,int>
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define pb(x) pupsh_back(x)
int32_t main() {
    int k;
    cin>>k;
    
    queue<string> Q;
    Q.push("1");
    Q.push("2");Q.push("3");Q.push("4");Q.push("5");Q.push("6");Q.push("7");Q.push("8");Q.push("9");
    
    int cnt=0;
    while(!Q.empty())
    {
        cnt++;
        if(cnt==k)
        {
            cout<<Q.front();
            return 0;
        }
        string s=Q.front();
        Q.pop();
        
        if(s[s.size()-1]=='0')
        {
        
            Q.push(s+"0");
            Q.push(s+"1");
        }
        else if(s[s.size()-1]=='1')
        {
            Q.push(s+"0");
            Q.push(s+"1");
            Q.push(s+"2");
        }
        else if(s[s.size()-1]=='2')
        {
            Q.push(s+"1");
            Q.push(s+"2");
            Q.push(s+"3");
        }
        else if(s[s.size()-1]=='3')
        {
            Q.push(s+"2");
            Q.push(s+"3");
            Q.push(s+"4");
        }
        else if(s[s.size()-1]=='4')
        {
            Q.push(s+"3");
            Q.push(s+"4");
            Q.push(s+"5");
        }
        else if(s[s.size()-1]=='5')
        {
            Q.push(s+"4");
            Q.push(s+"5");
            Q.push(s+"6");
        }
        else if(s[s.size()-1]=='6')
        {
            Q.push(s+"5");
            Q.push(s+"6");
            Q.push(s+"7");
        }
        else if(s[s.size()-1]=='7')
        {
            Q.push(s+"6");
            Q.push(s+"7");
            Q.push(s+"8");
        }
        else if(s[s.size()-1]=='8')
        {
            Q.push(s+"7");
            Q.push(s+"8");
            Q.push(s+"9");
        }
        else if(s[s.size()-1]=='9')
        {
            Q.push(s+"8");
            Q.push(s+"9");
        }
    }
    return 0;
    
//    cout<<"Sum of x+y = " << z;
}

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

int main() {
    
    int n, s[10001], q, t, count = 0;
    
    bool check = false;
    
    cin >> n;
    
    for (int i = 0; i < n; i ++) {
        
        cin >> s[i];
        
    }
    
    cin >> q;
    
    for (int i = 0; i < q; i ++) {
        
        cin >> t;
        
        for (int j = 0; j < n; j ++) {
        
            if (t == s[j]) {
                
                check = true;
                
            }
            
            //cout << t << ' ' << s[j] << ' ' << check << ' ' << endl;
        
        }
        
        if (check == true) {
            
            count += 1;
            
        }
        
        check = false;
        
    }
    
    cout << count << endl;
    
    return 0;
    
}


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

int main() {
  int n,a; cin >> n >> a;
  n = n%500;
  if(n <= a){
    cout << "Yes";
  }
  else{
    cout << "No";
  }
}

Measured memory_bytes: 3596
n,k=map(int,input().split())
s=str(input())
k = k-1
head = s[:k]
tail = s[k+1:]
mid = s[k]
if mid == "A":
    print(head+"a"+tail)
elif mid == "B":
    print(head+"b"+tail)
else:
    print(head+"c"+tail)

Measured memory_bytes: 38384
/*..........AAKASH GOYAL............*/
/*............DAIICT................*/
 
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
 

#define    int                      long long int
#define    f(i,j,n)                 for(int i = j; i <= n; i++)
#define    r(i,n,j)                 for(int i = n; i >= j; i--)
#define    mod                      1000000007
#define    speed                    ios_base::sync_with_stdio(false);
#define    upp                      cin.tie(NULL);
#define    pb                       push_back
#define    mp                       make_pair
#define    T                        int tt; cin >> tt; while(tt--)
#define    ff                       first
#define    ss                       second
#define    all(container)           container.begin() , container.end()
#define    sz(container)            (int)container.size()
#define    pii                      pair <int , int>
#define    pll                      pair <long long int , long long int>
#define    ppl                      pair < int , pll>              //pair of ll and pair ll 
#define    sp(x)                    setprecision(x)
 
int32_t main()
{       
    speed upp
    int n,k;
    cin>>n>>k;
    int a[n+1];
    f(i,1,n)
        cin>>a[i];
    int dp[n+1][k+1],pre[n+1][k+1];;
    memset(dp,0,sizeof(dp));
    f(i,0,n)
        dp[i][0]=1;
    f(i,0,a[1])
        dp[1][i]=1;
    f(i,0,n)
        pre[i][0]=1;
    f(i,1,k)
        pre[1][i]=(pre[1][i-1]+dp[1][i])%mod;
   
    f(i,2,n)
    {
        f(j,1,k)
        {
            if(j<=a[i])
                dp[i][j]=pre[i-1][j]%mod;
            else
                dp[i][j]=(pre[i-1][j]-pre[i-1][j-a[i]-1] + mod)%mod;
            pre[i][j]=(pre[i][j-1]+dp[i][j])%mod;
        }
    }
    cout<<dp[n][k];
}

Measured memory_bytes: 157568
n, *A = map(int, open(0).read().split())
B = [0] * len(A)
x = 0
B[0] = 1
for i in range(n):
  x = A[x]-1
  if B[x]:
    print(-1)
    exit()
  if x == 1:
    print(i+1)
    exit()
  B[x] = 1

Measured memory_bytes: 14068
#include <iostream>
#include <vector>
#include <string>

using namespace std;

void solve()
{
	string str;
	while(cin >> str)
	{
		vector< vector<int> > digits(10, vector<int>(10));
		for(int i = 0; i < 10; ++i)
		{
			digits[0][i] = str[i] - '0';
		}
		for(int i = 0; i < 9; ++i)
		{
			for(int j = 0; j < 9 - i; ++j)
			{
				digits[i + 1][j] = (digits[i][j] + digits[i][j + 1]) % 10;
			}
		}
		cout << digits[9][0] << endl;
	}
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 1204
S = input()
S_list = list(S)
S_length = len(S)
Count = 0

for i in range(S_length-1):
    if S_list[i] == S_list[i+1]:
        Count += 1
        if S_list[i+1] == "0":
            S_list[i+1] = "1"
        else:
            S_list[i+1] = "0"
    else:
        continue

print(Count)

Measured memory_bytes: 3956
S = input().split()
N = int(S[0])
M = int(S[1])
A = list(map(int, input().split()))
B = list(map(int, input().split()))
 
A_MAX = max(A)
B_MAX = max(B)
MAX = A_MAX if (A_MAX > B_MAX) else B_MAX
 
mod = int(1e9 + 7)
 
A_F_cnt = 0
B_F_cnt = 0
 
result = 1
 
for i in range(MAX, 0, -1):
    in_A = (i in A)
    in_B = (i in B)
    if (in_A and in_B):
        A_F_cnt += 1
        B_F_cnt += 1
    elif (in_A):
        result *= B_F_cnt
        result %= mod
        A_F_cnt += 1 
    elif (in_B):
        result *= A_F_cnt
        result %= mod
        B_F_cnt += 1
    else:
        coef = ( ( A_F_cnt * B_F_cnt )%mod - (N*M - i) )
        if coef < 0:
            coef += mod
        result *= coef
        result %= mod
        
    # print(in_A, in_B, A_F_cnt, B_F_cnt, result)
 
print(result % mod)


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


int ab, bc, ca;


int main() {
    cin >> ab >> bc >> ca;
    int ans = ab * bc / 2;
    cout << ans << endl;
}


Measured memory_bytes: 256
//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define s(x) scanf("%d",&x)
#define rep(i,x) for(int i=0;i<x;i++)
#define a first
#define b second
P bug[300005];

ll bit[(1<<17)+1]={};
ll bit2[(1<<17)+1]={};
int v[1<<17]={};
void add(int i,ll x)
{
	while(i<=(1<<17))
	{
		bit[i]+=x;
		i += (i & -i);
	}
}
ll sum(int i)
{
	ll s=0LL;
	while(i>0)
	{
		s+=bit[i];
		i -= (i & -i);
	}
	return s;
}
void add2(int i,ll x)
{
	while(i<=(1<<17))
	{
		bit2[i]+=x;
		i += (i & -i);
	}
}
ll sum2(int i)
{
	ll s=0LL;
	while(i>0)
	{
		s+=bit2[i];
		i -= (i & -i);
	}
	return s;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		ll x,y;
		scanf("%lld %lld",&x,&y);
		bug[i]=mp(y,x);
		v[x]++;
	}
	sort(bug,bug+n,greater<P>());
	int ret=0;
	for(int i=0;i<n;i++)
	{
		ll bord=bug[i].first;
		add(bug[i].second,bug[i].second);
		add2(bug[i].second,1LL);
		int lb=0;
		int ub=(1<<17);
		int maxv=0;
		while(ub-lb>1)
		{
			int mid=(lb+ub)>>1;
			ll s1=sum(mid);
			ll s2=sum2(mid);
			if(s1<=bord*s2) {lb=mid; maxv=max(maxv,(int)s2); continue;}
			for(int j=1;j<v[mid];j++)
			{
				if(s1-mid*j<=bord*(s2-j)) { lb=mid; maxv=max(maxv,(int)s2-j); break;}
			}
			ub=mid;
		}
		ret=max(ret,maxv);
		//printf("%lld %lld\n",sum(lb),sum2(lb));
		//if(sum(lb+1)<=sum2(lb+1)*bord) ret=max(ret,(int)sum2(lb+1));
		//printf("%d\n",maxv);
		
	}
	printf("%d\n",ret);
}

Measured memory_bytes: 8104
#include<iostream>
using namespace std;
int main()
{
    int L,R,d;
    cin >> L >> R >> d;
    if(L % d != 0){
	    cout << (R/d)-(L/d);
    } else {
		cout << (R/d)-(L/d)+1; 
    }
   return 0;
}

Measured memory_bytes: 3184
#include <algorithm>
#include <set>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <limits>
#include <memory>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#define all(a) (a).begin(), (a).end()
#define sz(a) static_cast<int>((a).size())
#define fillchar(a, x) memset(a, x, sizeof(a))
#define rep(i, a, b) for(int i=int(a); i<=int(b); ++i)
#define irep(i, a, b) for(int i=int(a); i>=int(b); --i)
#define replr(i, a, b) rep(i, a, (b)-1)
#define reprl(i, a, b) irep(i, (b)-1, a)
#define repn(i, n) rep(i, 0, (n)-1)
#define irepn(i, n) irep(i, (n)-1, 0)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef vector<LL> VL;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<string> VS;
template<class T, class S> ostream& operator<<(ostream& os, const pair<T, S>& v) { return os<<"("<<v.first<<", "<<v.second<<")"; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { os<<"["; repn(i, sz(v)) { if(i) os<<", "; os<<v[i]; } return os<<"]"; }
template<class T> bool setmax(T &_a, T _b) { if(_b>_a) { _a=_b; return true; } return false; }
template<class T> bool setmin(T &_a, T _b) { if(_b<_a) { _a=_b; return true; } return false; }
template<class T> T gcd(T _a, T _b) { return _b==0?_a:gcd(_b,_a%_b); }

int main() {
    ios_base::sync_with_stdio(false);

    int n, m, num; cin>>n>>m>>num;
    set<PII> painted, care;
    repn(i, num) {
        int x, y; cin>>x>>y;
        painted.insert(mp(x, y));
        rep(dx, -2, 0) rep(dy, -2, 0) {
            const int x0=x+dx, y0=y+dy;
            if(x0>=1 && x0<=n-2 && y0>=1 && y0<=m-2) {
                care.insert(mp(x0, y0));
            }
        }
    }
    VI ans(10);
    LL ans0=LL(n-2)*LL(m-2);
    for(const auto& p: care) {
        int cnt=0;
        repn(dx, 3) repn(dy, 3) {
            const int x0=p.fi+dx, y0=p.se+dy;
            if(painted.count(mp(x0, y0))) ++cnt;
        }
        ans[cnt]++, ans0--;
    }
    cout<<ans0<<endl;
    rep(i, 1, 9) cout<<ans[i]<<endl;

    return 0;
}


Measured memory_bytes: 47104
class Problem
  attr_accessor :n, :a, :b, :h, :w, :s, :seen
  def initialize
    @h, @w = gets.to_s.split.map{ |v| v.to_i }
    @s = Array.new(h){ gets.chomp }
    @seen = Array.new(h){ Array.new(w, -1) }
  end

  def solve
    bfs
    puts len == -1 ? -1 : white - len
  end

  def len
    @len ||= seen[-1][-1]
  end

  def bfs
    que = [[0,0]]
    seen[0][0] = 1
    while que.size > 0
      y, x = que.shift
      return if y == h - 1 && x == w - 1
      dist = seen[y][x]
      each(y, x) do |ny, nx|
        next if seen[ny][nx] != -1
        next if s[ny][nx] == "#"
        seen[ny][nx] = dist + 1
        que << [ny, nx]
      end
    end
  end

  def each(y, x)
    yield y + 1, x if y < h - 1
    yield y - 1, x if y > 0
    yield y , x + 1 if x < w - 1
    yield y , x - 1 if x > 0
  end

  def white
    @white ||= s.map{ _1.count(".") }.sum
  end
end

pb = Problem.new
pb.solve
# pp pb if ENV['USER'] == 'tamura'

Measured memory_bytes: 14320
import Control.Monad

main = do
    [h,w,a,b] <- map read.words<$>getLine
    replicateM_ b $ putStrLn $ replicate a '0' ++ replicate (w-a) '1'
    replicateM_ (h-b) $ putStrLn $ replicate a '1' ++ replicate (w-a) '0'

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

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

  if (S.at(S.size() -1 ) == 's'){
    cout << S  <<"es" << endl;
  }
  else{
    cout << S << "s" << endl;
  }
}

Measured memory_bytes: 3620
import Control.Applicative

dayCount [] = return ()
dayCount (x:xs) = do
  let day = (head xs) + case x of 0 -> 0
                                  1 -> 0
                                  2 -> 31
                                  3 -> 60
                                  4 -> 91
                                  5 -> 121
                                  6 -> 152
                                  7 -> 182
                                  8 -> 213
                                  9 -> 244
                                  10 -> 274
                                  11 -> 305
                                  12 -> 335
  if day == 0
    then return ()
    else case mod day 7 of 0 -> putStrLn "Wednesday"
                           1 -> putStrLn "Thursday"
                           2 -> putStrLn "Friday"
                           3 -> putStrLn "Saturday"
                           4 -> putStrLn "Sunday"
                           5 -> putStrLn "Monday"
                           6 -> putStrLn "Tuesday"

main = do
  input <- fmap (fmap (read :: String -> Int) . words) . lines <$> getContents
  mapM_ dayCount input

Measured memory_bytes: 3968
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define repp(i, m, n) for(int i = m; i < n; i++)
#define reps(i, n) for(int i = 1; i <= n; i++)
const int    INF = 100000000;
const double EPS = 1e-10;
const int    MOD = 1000000007;
using namespace std;
typedef long long ll;
typedef pair<int, int> pai;
typedef pair<ll,ll> pal;



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

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"math"
	"strconv"
	"strings"
)

func main() {

	var a, b int
	fmt.Scan(&a, &b)

	var r1 = a*b == 15
	var r2 = a+b == 15

	if !r1 && !r2 {
		fmt.Printf("x")
	} else if r1 {
		fmt.Printf("*")
	} else if r2 {
		fmt.Printf("+")
	}
}

func ScanIntN(r *bufio.Reader, ints []int) {

	line, e := r.ReadString('\n')
	strs := strings.Split(line, " ")
	for i, str := range strs {
		trimed := strings.TrimSpace(str)
		ints[i], e = strconv.Atoi(trimed)
		if e != nil {
			panic(e)
		}
	}
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func abs(i int) int {
	if i < 0 {
		return -i
	} else {
		return i
	}
}


Measured memory_bytes: 640
import java.util.*;
import java.awt.geom.*;
import java.awt.geom.Line2D.Double;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true){
			int n = sc.nextInt();
			if(n==0) break;
			
			double[] x = new double[2*n];
			double[] y = new double[2*n];
			Line2D.Double[] cross = new Line2D.Double[n];
			Line2D.Double p = new Line2D.Double();

			
			double xa = sc.nextDouble();
			double ya = sc.nextDouble();
			double ra = sc.nextDouble();
			double xb = 0;
			double yb = 0;
			double rb = 0;
			double a, b, c, A, B, C;
			
			x[0] = xa;
			y[0] = ya;
			for(int i=1;i<n;i++){
				xb = sc.nextDouble();
				yb = sc.nextDouble();
				rb = sc.nextDouble();
				
				A = xa-xb;
				B = ya-yb;
				C = (A*xa+A*xb+B*ya+B*yb+rb*rb-ra*ra)/2;
				if(A==0){
					c = (C/B-ya)*(C/B-ya)+xa*xa-ra*ra;
					x[2*i-1] = xa+Math.sqrt(xa*xa-c);
					x[2*i] = xa-Math.sqrt(xa*xa-c);
					y[2*i-1] = C/B;
					y[2*i] = C/B;
				}else if(B==0){
					c = (C/A-xa)*(C/A-xa)+ya*ya-ra*ra;
					y[2*i-1] = ya+Math.sqrt(ya*ya-c);
					y[2*i] = ya-Math.sqrt(ya*ya-c);
					x[2*i-1] = C/A;
					x[2*i] = C/A;
				}else{
					a = 1+(A*A)/(B*B);
					b = (2*A*ya*B-2*A*C-2*xa*B*B)/(B*B);
					c = (C/B-ya)*(C/B-ya)+xa*xa-ra*ra;
					x[2*i-1] = (-b+Math.sqrt(b*b-4*a*c))/(2*a);
					x[2*i] = (-b-Math.sqrt(b*b-4*a*c))/(2*a);
					y[2*i-1] = (C-A*x[2*i-1])/B;
					y[2*i] = (C-A*x[2*i])/B;
				}
				cross[i] = new Line2D.Double(x[2*i-1],y[2*i-1],x[2*i],y[2*i]);
				
				xa = xb;
				ya = yb;
				ra = rb;
			}
			x[2*n-1] = xb;
			y[2*n-1] = yb;
			
			double[][] cost = new double[2*n][2*n];
			for(int i=0;i<2*n;i++) Arrays.fill(cost[i], Integer.MAX_VALUE);			
			boolean flag;
			for(int i=0;i<2*n;i++){
				for(int j=i+1;j<2*n;j++){
					flag = false;
					p.setLine(x[i], y[i], x[j], y[j]);
					for(int k=(i+1)/2;k<(j+1)/2;k++){
						if(k!=0 && p.intersectsLine(cross[k])==false){
							flag = true;
							break;
						}
					}
					if(flag==false)	cost[i][j] = Math.sqrt((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));
				}
			}
			
			for(int i=0;i<2*n;i++) cost[i][i] = 0;
			for(int i=0;i<2*n;i++){
				for(int j=0;j<2*n;j++){
					for(int k=0;k<2*n;k++){
						if(cost[j][i]!=Integer.MAX_VALUE && cost[i][k]!=Integer.MAX_VALUE){
							cost[j][k] = Math.min(cost[j][k], cost[j][i]+cost[i][k]);
						}
					}
				}
			}
			System.out.println(cost[0][2*n-1]);
		}	
	}	
}

Measured memory_bytes: 51728
#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 vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

#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 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)

const double EPS = 1e-10;
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 main(void){
    int L; cin >> L;
    int one = 0, two = 0;
    REP(i,20){
        if(L & 1<<i){
            one++;
            chmax(two, i);
        }
    }
    int N = 20, M=19+(one-1)+two;
    cout << N << " " << M << endl;
    REP(i,N-1) cout << i+1 << " " << i+2 << " " << 0 << endl;
    REP(i,two) cout << N-1-i << " " << N-i << " " << (1<<i) << endl;

    REP(i,two){
        if(L & 1<<i){
            cout << 1 << " " << N-i << " " << (1<<two) + L%(1<<i) << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int i = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int i = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define MP make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1 << 30;
const ll LINF = 1LL << 61;
const int MOD = 1e9 + 7;

int check(int i, int j) {
    if((i + j) % 4 == 0)
        return 6;
    else if((i + j) % 4 == 2)
        return 1;
    else if(j % 4 == 1)
        return 3;
    else if(j % 4 == 3)
        return 4;
    else if(i % 4 == 1)
        return 2;
    else if(i % 4 == 3)
        return 5;
}

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

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> s(H);
    rep(i, H) cin >> s[i];
    vector<vector<bool>> ok(H, vector<bool>(W));
    rep(i, H) rep(j, W) {
        if(check(i, j) == s[i][j] - '0') {
            ok[i][j] = 1;
        }
    }
    vector<vector<bool>> reach(H, vector<bool>(W));
    queue<pii> que;
    que.push(MP(0, 0));
    reach[0][0] = 1;
    while(!que.empty()) {
        auto p = que.front();
        que.pop();
        int y = p.first;
        int x = p.second;
        rep(i, 4) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(nx >= 0 && nx < W && ny >= 0 && ny < H) {
                if(!reach[ny][nx] && ok[ny][nx]) {
                    reach[ny][nx] = 1;
                    que.push(MP(ny, nx));
                }
            }
        }
    }
    if(reach[H - 1][W - 1]) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}


Measured memory_bytes: 3256
#include <bits/stdc++.h>
using namespace std;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
int main()
{
    Hello
    int s, w;
    cin >> s >> w;
    if(w >= s)
        cout << "unsafe";
    else
        cout << "safe";
    return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int N,x;
    cin >> N >> x;
    vector<int> A(N);
    rep(i,0,N)cin >> A[i];
    sort(A.begin(), A.end());
    int sum = 0,cnt = 0;
    for(int i = 0;i < N;i++){
        sum += A[i];
        if(sum > x)break;
        cnt++;
    }
    if(sum < x)cnt--;
    cout << cnt << endl;

}

Measured memory_bytes: 256
import java.util.*;


public class Main {

	static void log(String s) {
		System.out.println(s);
	}

	static void log(int i) {
		System.out.println(i);
	}

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		
		String input = sc.next();		
		
		char array[] = input.toCharArray();
		
		boolean existBus = false;
		if(array[0]!=array[1])
			existBus =true;
		else if(array[1]!=array[2])
			existBus =true;
		else if(array[0]!=array[2]) {
			existBus = true;
		}
				
		log( existBus ? "Yes" : "No");	
	}

}


Measured memory_bytes: 22740
import sys
import  math
import fractions
from collections import defaultdict
import copy
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N=int(input())
A=nl()
mod=10**9+7
sum_a=sum(A)
ans=0
for i in range(N):
    sum_a=sum_a-A[i]
    ans+=sum_a*A[i]
    ans%=mod

print(ans)


    

Measured memory_bytes: 33120
while True:
    n, m, p = map(int, raw_input().split())
    if n == 0:
        break
    x = [int(raw_input()) for _ in range(n)]

    if x[m - 1] == 0:
        print 0
    else:
        print sum(x)*(100 - p) / x[m - 1]

Measured memory_bytes: 6264
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_cxx;
#define dprint(v) cout << #v"=" << v << endl //;)
#define sz(c) ((int)c.size())
#define zero(v) memset(v, 0, sizeof(v))
#define forall(it,v) for(auto it=v.begin();it!=v.end();++it)
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define INF (ll)1e16
#define endl '\n'
#define isin(x,y) ((y).find(x)!=(y).end())

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
#include <ext/pb_ds/assoc_container.hpp>  //--------> important header!
using namespace __gnu_pbds;              //--------> important namespace!

struct HASH{
  size_t operator()(const pair<int,int>&x)const{
    return (size_t) x.first * 37U + (size_t) x.second;
  }
};
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    ll n;
    cin>>n;
    bool done[10][10];
    memset(done,0,sizeof(done));
    string str;
    cin>>str;
    set<int> running;
    int a[n];
    forn(i,n)a[i]=str[i]-'0';
    vector<int> d(n);
    for(int i=n-1; i>=0; i--){
        running.insert(a[i]);
        d[i]=sz(running);
    }
    ll ans=0;
    forn(i,n-2){
        for(int j = i+1; j < n-1; j++){
            if(!done[a[i]][a[j]]){
                ans+=d[j+1];
                done[a[i]][a[j]]=1;
            }
        }
    }
    cout<<ans<<endl;
	return 0;
}


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

vector<ll> to[100010];

int main(){
    ll n;cin>>n;
    rep(i,0,n-1){
        ll a,b;cin>>a>>b;
        a--;b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    ll c[100010],an=0;
    rep(i,0,n){cin>>c[i];an+=c[i];}
    sort(c,c+n);
    an-=c[n-1];
    cout<<an<<endl;
    vector<ll> num(n,-1);
    queue<ll> q;
    num[0]=c[n-1];
    q.push(0);
    ll ite=n-2;
    while(!q.empty()){
        ll now=q.front();
        q.pop();
        for(auto nx:to[now]){
            if(num[nx]!=-1)continue;
            num[nx]=c[ite];
            ite--;
            q.push(nx);
        }
    }
    rep(i,0,n){
        cout<<num[i];
        if(i!=n-1)cout<<" ";
    }
    cout<<endl;
}







Measured memory_bytes: 3328
#include <bits/stdc++.h>
const int mod=998244353;
#define Rint register int
#define C(n,m) (n<m?0:1ll*fac[n]*invfac[n-m]%mod*invfac[m]%mod)
using namespace std;
int T,n,m,p,k,dp[3][100010],sg[100010],ans=0,ksm_18[100010];
bool vis[1010];
struct edge{
	int to,link,w;
};
struct graph{
	int head[100010],o;
	edge e[2000010];
	void clear(){
		memset(head,0,sizeof(head));
		o=0;
	}
	void add_edge(int u,int v){
		e[++o].to=v,e[o].link=head[u],head[u]=o;
		e[++o].to=u,e[o].link=head[v],head[v]=o;
	}
}g[3];
int main(){
	scanf("%d",&n);
	ksm_18[0]=1,ksm_18[1]=(1000000000000000000ll)%mod;
	for(int i=2;i<=n;i++) ksm_18[i]=1ll*ksm_18[i-1]*ksm_18[1]%mod; 
	for(int t=0;t<3;t++){
		scanf("%d",&m);
		for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),g[t].add_edge(u,v);
		for(int u=n;u>=1;u--){
			sg[u]=0;
			for(int i=g[t].head[u];i;i=g[t].e[i].link) if(g[t].e[i].to>u) vis[sg[g[t].e[i].to]]=true;
			while(vis[sg[u]]) sg[u]++;
//			cout<<sg[u]<<" ";
			dp[t][sg[u]]=(dp[t][sg[u]]+ksm_18[u])%mod;
			for(int i=g[t].head[u];i;i=g[t].e[i].link) if(g[t].e[i].to>u) vis[sg[g[t].e[i].to]]=false;
		}
//		cout<<"\n";
	}
	for(int i=0;i<=1000;i++) for(int j=0;j<=1000;j++) ans=(ans+1ll*dp[0][i]*dp[1][j]%mod*dp[2][i^j])%mod;
	printf("%d\n",ans);
}


Measured memory_bytes: 12796
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1001001001;

// dp
// 薬品i番目までで、Aをj(g)、Bをk(g)の溶液を作るときの最小コスト
int dp[41][405][405];

int main(){
    int n, ma, mb;
    cin >> n >> ma >> mb;
    vector<int> a(n), b(n), c(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i] >> b[i] >> c[i];
    }

    // dpテーブルの初期化
    for(int i = 0; i <= 40; ++i){
        for(int j = 0; j <= 400; ++j){
            for(int k = 0; k <= 400; ++k){
                dp[i][j][k] = INF;
            }
        }
    }
    dp[0][0][0] = 0;

    int budget = INF;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j <= 400; ++j){
            for(int k = 0; k <= 400; ++k){
                // 薬品iを入れない場合
                dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k]);

                // (j,k)が比の条件(ma:mb)を満たしていれば、budgetと比較する
                if((j != 0 && k != 0) && j*mb == k*ma){
                    budget = min(budget, dp[i+1][j][k]);
                }

                // 薬品iを入れる場合
                if(j+a[i] <= 400 && k+b[i] <= 400){
                    dp[i+1][j+a[i]][k+b[i]] = min(dp[i][j][k]+c[i], dp[i+1][j+a[i]][k+b[i]]);

                    // (j,k)が比の条件を満たしていれば、budgetと比較
                    if((j+a[i])*mb == (k+b[i])*ma){
                        budget = min(budget, dp[i+1][j+a[i]][k+b[i]]);
                    }
                }
            }
        }
    }

    if(budget == INF)   budget = -1;
    cout << budget << endl;
}

Measured memory_bytes: 26496
// https://atcoder.jp/contests/abc126/tasks/abc126_c

package main

import "fmt"
import "bufio"
import "os"
import "strconv"

import "math"

var _sw = bufio.NewScanner(os.Stdin)

func main() {
	N := float64(nextInt())
	K := float64(nextInt())

	p1 := (N - K + 1) / N
	if p1 < 0 {
		p1 = 0
	}

	maxPow := math.Ceil(math.Log2(K))
	sum := 0.0
	for i := 1; i <= int(math.Min(K-1, N)); i++ {
		sum += math.Pow(2, maxPow-(math.Ceil(math.Log2(K/float64(i)))))
	}

	p2 := sum / math.Pow(2, maxPow)

	fmt.Println(p1 + p2/N)
}

func init() {
	_sw.Split(bufio.ScanWords)
}

func nextInt() int {
	if _sw.Scan() == false {
		panic(_sw.Err())
	}
	i, e := strconv.Atoi(_sw.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func nextString() string {
	if _sw.Scan() == false {
		panic(_sw.Err())
	}
	return _sw.Text()
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}


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

int main()
{
	string s;
	int i,flag=0;

	cin>>s;

	for(i=0;i<3;i++)
	{
		if(s[i]==s[i+1])
		{
			flag=1;
			break;
		}
	}
	if(flag)
		cout<<"Bad";
	else
		cout<<"Good";

	return 0;
}

Measured memory_bytes: 256
<?php
$nl=trim(fgets(STDIN));

$node=array($nl);

for($i=0;$i<$nl;$i++){$node[$i]=array('ch'=>array(),'pa'=>-1);}

for($i=0;$i<$nl;$i++){
	$ls=explode(' ',trim(fgets(STDIN)));#lines

	$id=(int)array_shift($ls);
	$cl=(int)array_shift($ls);#child length

	$node[$id]['ch']=$ls;#child

	for($j=0;$j<$cl;$j++){#child's parent is id
		$node[$ls[$j]]['pa']=$id;
	}
}

for($i=0;$i<$nl;$i++){
	$ni=$node[$i];#id=i
	$ch=implode(', ',$ni['ch']);
	$ty='root';#type
	$de=0;#depth

	if($ni['pa']!=-1){
		$de=1;
		$nt=$ni['pa'];
		while($node[$nt]['pa']!=-1){
			++$de;
			$nt=$node[$nt]['pa'];
		}
		$ty=(count($ni['ch']))? 'internal node':'leaf';
	}

	printf("node %d: parent = %d, depth = %d, %s, [%s]\n"
		,$i
		,$ni['pa']
		,$de
		,$ty
		,$ch
	);
}

Measured memory_bytes: 109636