akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

//.define
// #define FILE_IN_OUT
#define RET(_x)    return cout << (_x) << '\n', 0;
#define all(_obj)  (_obj).begin(), (_obj).end()
#define loop(_n)   for (int i = 0; i < (_n); ++i)
#define sz(_obj)   static_cast<int>((_obj).size())
#ifdef SHJ_LOCAL
#define debug(_x)  std::cerr << (#_x) << " = " << (_x) << '\n' << std::flush;
#else
#define debug(_x)  {}
#endif
#define endl "\n"
template<typename P, typename Q>
P CeilDiv(P _dividend, Q _divider) {
    return static_cast<P>((_dividend - 1LL + _divider) / _divider);
}
template<typename Tp>
inline void outarr(Tp _begin, Tp _end, const char* _delim = " ") {
    for (Tp current = _begin; current != _end; ++current) {
        std::cout << *current << _delim;
    }
    std::cout << '\n';
}

//.constant
using ll  = long long;
using pii = std::pair<int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr int MOD = static_cast<const int>(1e9 + 7);

//.data

//.code
int main() {
#ifdef FILE_IN_OUT
    std::ifstream cin ("input.txt",  std::ios::in);
    std::ofstream cout("output.txt", std::ios::out);
#else
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
#endif

    int n;
    cin >> n;
    vector<int> arr(n);
    loop(n) {
        cin >> arr[i];
    }
    ll ans = 0;
    int maxx = arr[0];
    for (int i = 1; i < n; ++i) {
        if (arr[i] < maxx) {
            ans += maxx - arr[i];
        }
        maxx = max(arr[i], maxx);
    }
    cout << ans << endl;

#ifdef FILE_IN_OUT
    cin.close();
    cout.close();
#endif
    return 0;
}

Measured memory_bytes: 3984
#include <bits/stdc++.h>
using namespace std;
 
long long N, ans, M, cnt[26];
char S;
 
int main() {
  M = 1e9 + 7;
  cin >> N;
 
  for (int i = 0; i < N; i++) {
    cin >> S;
    cnt[S - 'a']++;
  }
 
  ans = 1;
  for (int i = 0; i < 26; i++) {
    ans *= (cnt[i] + 1);
    ans %= M;
  }
 
  cout << ans - 1 << '\n';
 
  return 0;
}


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

int main() {
    long long n, a; cin >> n >> a;
    long long ans = n;
    
    for(int amount = 1; 1LL * (amount / 2) * (amount / 2) <= 2 * n; ++amount) {
        if(1LL * (amount / 2) * (amount / 2 + amount % 2) >= n) {
            ans = min(ans, amount + a);
            break;
        }
    }

    for(int steps = 3; steps <= 50 && 1LL * (steps - 1) * a <= ans; ++steps) {
        for(int amount = 1; amount <= 30000; ++amount) {
            long long small = amount / steps;
            long long large = amount / steps + 1;
            int manyLarge = amount % steps;

            long long elem = 1;
            for(int i = 0; i < manyLarge; ++i)
                elem *= large;
            for(int i = 0; i < steps - manyLarge; ++i)
                elem *= small;
            if(elem >= n) {
                ans = min(ans, 1LL * (steps - 1) * a + amount);
                break;
            }
        }
    }

    cout << ans << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#ifdef XVENOM
	#define errp(...) fprintf(stderr, __VA_ARGS__)
	#define dbg(...) errp("[%s]: ", #__VA_ARGS__), dbg_str(__VA_ARGS__)
#else
	#define errp(...)
	#define dbg(...)
#endif
template <typename U, typename V> string to_string (pair<U, V>);
string to_string (const string& e_) { return "\"" + e_ + "\""; }
string to_string (char e_) { return "\'" + string(1, e_) + "\'"; }
string to_string (bool e_) { return e_ ? "true" : "false"; }
template <typename T> string to_string (T e_) {
	string s_ = "[ ";
	for (const auto& x_ : e_) s_ += to_string(x_) + " ";
	return s_ + "]";
}
template <typename U, typename V> string to_string (pair<U, V> e_) {
	return "(" + to_string(e_.first) + ", " + to_string(e_.second) + ")";
}
void dbg_str () { errp(" \n"); }
template <typename U, typename... V> void dbg_str (U u, V... v) {
	errp(" %s", to_string(u).c_str()); dbg_str(v...);
}
/* --- */
const int N = 100010;
int h[N];

int mincount(int level, int start, int end){
	if(start > end) return 0;
	if(start == end) return (h[start] - level);
	
	int minindex, min = h[start];
	for(int i = start; i <= end; i++){
		if(min >= h[i]){
			min = h[i];
			minindex = i;
		}
	}
	return mincount(h[minindex],start,minindex-1) + mincount(h[minindex],minindex+1,end) + (h[minindex]-level);
}

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	/* --- */
	int n;
	cin >> n;

	for(int i = 0; i < n; i++) cin >> h[i];

	cout << mincount(0,0,n-1);
}	

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <unistd.h>
#include <sys/stat.h>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <random>
#include <string.h>      //文字列の代入に使う
#include <bits/stdc++.h> //piの利用で必要(M_PI)
#include <algorithm>
#include <climits>

int main()
{
    int N, grandsum = INT_MAX;
    std::cin >> N;

    std::vector<int> X(N);
    for (int i = 0; i < N; i++)
    {
        std::cin >> X.at(i);
    }
    //各座標ごとの全員の体力の消耗をいちいち計算する．
    for (int i = 1; i <= 100; i++)
    {
        int sum = 0;
        for (int j = 0; j < N; j++)
        {
            sum += pow(X.at(j) - i, 2);
        }
        grandsum = std::min(grandsum, sum);
    }

    std::cout << grandsum << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
typedef long long ll;
const ll MOD=1000000007;
using namespace std;
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; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }

int main(void){
    // Your code here!
    int n; cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    int two = 0;
    int four = 0;
    rep(i,n) {
        if (a[i] %2 == 0 && a[i] % 4 !=0){
            two++;
        }
        else if (a[i] % 4 == 0){
            four++;
        }
    }
    int res = four + two/2;
    if (res >= n/2) cout << "Yes" << endl;
    else cout << "No" << endl;
}


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

char F[102][102];

void
DFS (int Y, int X, char A)
{
  if (F[Y][X] != A)
    return;

  F[Y][X] = '.';

  DFS (Y - 1, X, A);
  DFS (Y, X + 1, A);
  DFS (Y + 1, X, A);
  DFS (Y, X - 1, A);
}

int
main ()
{
  int N, M;
  int cnt;

  while (true)
    {

      cin >> N >> M;
      cnt = 0;
      if (N == 0 && M == 0)
	break;

      for (int y = 1; y <= N; y++)
	{
	  for (int x = 1; x <= M; x++)
	    {
	      cin >> F[y][x];
	    }
	}

      for (int y = 1; y <= N; y++)
	{
	  for (int x = 1; x <= M; x++)
	    {
	      if (F[y][x] == '@' || F[y][x] == '#' || F[y][x] == '*')
		{
		  cnt++;
		  DFS (y, x, F[y][x]);
		}
	    }
	}



      cout << cnt << endl;
    }





  return 0;
}

Measured memory_bytes: 3272
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

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

int bit[200010], n = 200010;

//0からi-1番目までの和
int sum(int i) {
  i++;
  int s = 0;
  while(i > 0) {
    s += bit[i];
    i -= i&-i;
  }
  return s;
}

//i番目(0-index)にxを加える
void add(int i, int x) {
  i++;
  while(i <= n) {
    bit[i] += x;
    i += i&-i;
  }
}

int cnt[30], idx[30], a[200010];
deque<int> idx2[30];
signed main(void)
{
  string s;
  cin >> s;
  REP(i, s.size()) cnt[s[i]-'a']++;

  int tmp = 0;
  REP(i, 26) if(cnt[i]%2) tmp++;
  if(tmp >= 2) {
    cout << -1 << endl;
    return 0;
  }

  string t1 = "", t2 = "", t3 = "";
  REP(i, s.size()) {
    if(cnt[s[i]-'a']%2) {
      if(idx[s[i]-'a'] < cnt[s[i]-'a']/2) a[i] = 0;
      else if(idx[s[i]-'a'] == cnt[s[i]-'a']/2) a[i] = 1;
      else if(idx[s[i]-'a'] > cnt[s[i]-'a']/2) a[i] = 2;
    } else {
      if(idx[s[i]-'a'] < cnt[s[i]-'a']/2) a[i] = 0;
      else a[i] = 2;
    }
    if(a[i] == 0) t1 += s[i];
    else if(a[i] == 1) t2 += s[i];
    else t3 += s[i];
    idx[s[i]-'a']++;
  }
  reverse(ALL(t1));

  // t3をt1に合わせる
  REP(i, t1.size()) idx2[t1[i]-'a'].push_front(i+s.size()/2+!!(s.size()%2));
  VI v2;
  REP(i, t3.size()) {
    v2.PB(idx2[t3[i]-'a'].back());
    idx2[t3[i]-'a'].pop_back();
  }

  // 回文にした後で移るindex
  VI v;
  int id = 0, id2 = 0;
  REP(i, s.size()) {
    if(a[i] == 0) {
      v.PB(id++);
    } else if(a[i] == 1) {
      v.PB(s.size()/2);
    } else {
      v.PB(v2[id2++]);
    }
  }

  // vの転倒数を求める
  ll ans = 0;
  REP(i, v.size()) {
    ans += i - sum(v[i]);
    add(v[i], 1);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 7804
import bisect, collections, copy, heapq, itertools, math, numpy, string
import sys
from bisect import bisect_left, bisect_right, insort
from collections import deque
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def MS(): return map(str, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
# N = I()
# A = [LI() for _ in range(N)]


n = I()
a = LI()
box = [0] * 100000
q = I()
for i in range(n):
    box[a[i]-1] += 1
ans = 0
for i in range(len(box)):
    ans += (i+1) * box[i]

for i in range(q):
    b,c = MI()
    x = box[b-1]
    box[c-1] += x
    box[b-1] = 0
    ans += c * x - b*x
    print(ans)



Measured memory_bytes: 38688
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll linf = (1ll << 61);
const int inf = 1001001001;
const int mod = 1000000007;

int mp[3][3];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	rep(i, 3)rep(j, 3) cin >> mp[i][j];
	rep(a, 101)rep(b, 101) {
		if (a + b != mp[0][0]) continue;
		vector<int> a_(3), b_(3);
		rep(i, 3) a_[i] = mp[0][i] - b;
		rep(i, 3) b_[i] = mp[i][0] - a;
		bool ok = true;
		rep(i, 3)rep(j, 3) {
			if (mp[i][j] != a_[j] + b_[i]) ok = false;
		}
		if (ok) {
			printf("%s\n", "Yes");
			return 0;
		}
	}
	printf("%s\n", "No");
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define ALL(a)    a.begin(), a.end() 
#define rep(i, K, N)  for(long long int i = K; i <= N; i++)
#define ll long long int
#define PP 1000000007
using namespace std;

map<ll, ll> M;

void prime_factor(ll N){

bool C = 1;

while(C){

C = 0;

    rep(i, 2, sqrt(N)){

    if(N%i == 0){M[i]++;N /= i;C = 1;break;}
   
    }

}

M[N]++;

}

int main() {
ll N, Ans = 1;cin >> N;

rep(i, 2, N){

  prime_factor(i);

}

for(auto x : M ){

  Ans *= x.second + 1;Ans %= PP;

}

cout << Ans;

}

Measured memory_bytes: 3668
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,t,flag;
    cin>>n;
    while(n!=0)
    {
        t=n%10;
        n=n/10;
        if(t==7)
        {
            flag=1;
            break;
        }
        else
            flag=0;
    }
    if(flag==1)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;

}


Measured memory_bytes: 3636
import java.awt.geom.Point2D;
import java.util.*;

public class Main {
	Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		new Main();
	}

	public Main() {
		while(in.hasNext())new AOJ1134().doIt();
	}

	class AOJ1134{
		final double EPS=1.0e-8;
		Point2D[] intersectPtCC(Circle a,Circle b){
			double dis = a.p.distance(b.p);
			if(dis > a.r+b.r) return null;
			Point2D v = sub(b.p, a.p);
			double rc = (dis*dis + a.r*a.r - b.r*b.r)/(2*dis); 
			double rate = rc/dis;
			v = mul(rate, v);
			Point2D c = add(v, a.p);
			double disC2c = c.distance(b.p);
			double disqc = Math.sqrt(b.r*b.r - disC2c*disC2c);
			Point2D v2 = sub(b.p, c);
			v2 = mul(disqc/disC2c, v2);
			Point2D[] ret = new Point2D.Double[2];
			ret[0] = add(normalVector1(v2), c);
			ret[1] = add(normalVector2(v2), c);
			return ret;
		}

		Point2D add(Point2D p1,Point2D p2){
			return new Point2D.Double(p1.getX()+p2.getX(), p1.getY()+p2.getY());
		}
		
		Point2D normalVector1(Point2D p){
			return new Point2D.Double(-p.getY(), p.getX());
		}
		Point2D normalVector2(Point2D p){
			return new Point2D.Double(p.getY(), -p.getX());
		}
		
		Point2D mul(double n,Point2D p1){
			return new Point2D.Double(p1.getX()*n,p1.getY()*n);
		}

		Point2D sub(Point2D p1,Point2D p2){
			return new Point2D.Double(p1.getX()-p2.getX(),p1.getY()-p2.getY());
		}

		class Circle{
			Point2D p;
			double r;
			Circle(Point2D p,double r){ 
				this.p=p;
				this.r=r;
			}
			Circle(double x,double y,double r){  
				this.p=new Point2D.Double(x,y); 
				this.r=r;
			}
		}

		void doIt(){
			int n = in.nextInt();
			if(n==0)return;
			Point2D[] p = new Point2D[n];
			for(int i=0;i<n;i++)p[i] = new Point2D.Double(in.nextDouble(),in.nextDouble());
			int result = 1;
			for(int i=0;i<n;i++)for(int s=0;s<n;s++)if(i!=s)if(p[i].distance(p[s])<=2){
				Point2D[] k = intersectPtCC(new Circle(p[i], 1), new Circle(p[s], 1));
				for(int a=0;a<k.length;a++){
					int cnt = 0;
					for(int b=0;b<n;b++)if(k[a].distance(p[b])<=1+EPS)cnt++;
					result = Math.max(result, cnt);
				}
			}
			System.out.println(result);
		}
	}
}

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

using namespace std;

int main(){
    
    int n, x;
    vector<int> m;

    cin >> n >> x;

    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        m.emplace_back(tmp);
    }

    for(auto it = m.begin(); it < m.end(); it++){
        if(it == min_element(m.begin(), m.end())){
            continue;
        }

        x -= *it;
    }

    cout << x / *min_element(m.begin(), m.end()) + n - 1 << endl;
    
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.stream.Stream;
import java.util.Arrays;

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        String str = sc.next();
        sc.close();
        long count = 0;

        String[] strList = str.split("");
        long white = Stream.of(strList).filter(e -> e.equals("W")).count();
        long red = n - white;
        String[] copyList = strList.clone();
        Arrays.sort(copyList);
        
        for(int i = 0; i < n; i++){
            if(!strList[i].equals(copyList[i])){
                count++;
            }
        }
        count = count / 2;
        System.out.println(Math.min(white, Math.min(red, count)));
    }
}

Measured memory_bytes: 66064
#include<stdio.h>

int main(void){
int n,k;
  scanf("%d %d", &n,&k);
  int p[n];
  
   int i,j;
  
   for (i=0; i<n; ++i)
    scanf("%d", &p[i]);

  int tmp;
   for (i=0; i<n; ++i) {
    for (j=i+1; j<n; ++j) {
      if (p[i] > p[j]) {
        tmp =  p[i];
        p[i] = p[j];
        p[j] = tmp;
      }
    }
  }
int answer=0;
  for(i=0;i<k; ++i){
  answer += p[i];
  }
  printf("%d",answer);
  return 0;
}

Measured memory_bytes: 2156
Module Module1

    Sub Main()
        'let
        Dim tmp As String() = Split(Console.ReadLine())
        Dim a As Long = tmp(0)
        Dim b As Long = tmp(1)
        Dim arr = New String() {"Odd", "Even"}

        'var
        Dim ans As String

        ans = arr(Math.Abs(CLng(a Mod 2 = 0 Or b Mod 2 = 0)))
        Console.WriteLine(ans)

    End Sub

End Module

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

int main() {
    int ans = 0;
    int N;
    cin >> N;
    vector<ll> L(N);
    rep(i, N) cin >> L[i];
    sort(L.begin(), L.end(), greater<ll>());
    for(int i = 0; i < N; i++) {
        for(int j = i + 1; j < N; j++) {
            for(int k = j + 1; k < N; k++) {
                if(L[i] == L[j] || L[j] == L[k] || L[k] == L[i])
                    continue;
                else if(L[i] < L[j] + L[k])
                    ans++;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin>>n;
  bool ans=true;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin>>a.at(i);
  }
  for(int i=0;i<n;i++){
    if(a.at(i)%2==0){
      if(a.at(i)%3!=0 && a.at(i)%5!=0){
        ans=false;
      }
    }
  }
  if(ans){
    cout<<"APPROVED";
  }
  else{
    cout<<"DENIED";
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)


int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    string t;
    for(int i=2*n-1;i>=n;i--){
        t.push_back(s[i]);
    }
    ll ans = 0;
    for(int bit = 0;bit<(1<<n);bit++){
        string s1,s2;
        int cnt = 0;
        for(int i=0;i<n;i++){
            if((bit>>i)&1){
                s1.push_back(s[i]);
                cnt++;
            }else{
                s2.push_back(s[i]);
            }
        }
        ll dp[20][20][20]={};
        dp[0][0][0] = 1;
        for(int i=0;i<n;i++){
                for(int j=1;j<=max(i+1,cnt);j++){
                    if(t[i]==s1[j-1])dp[i+1][j][i+1-j] +=dp[i][j-1][i+1-j];
                }
                for(int k=1;k<=max(i+1,n-cnt);k++){
                    if(t[i]==s2[k-1])dp[i+1][i+1-k][k] +=dp[i][i+1-k][k-1];
                }
                
        }
        //cout << s1 << " " << s2 << " " << cnt<< endl;
        ans += dp[n][cnt][n-cnt];
        //cout << ans << endl;
        //if(bit%1000==0)cout << bit << endl;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
#pragma GCC optimize("Ofast")  
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long 
#define endl "\n"
#define all(x) (x).begin(),(x).end()
const int MOD = 1e9+7;
const int mxN = 2e5+3;

int powmod(int x, int y){
	int res = 1;
	x %= MOD;
	while(y > 0){
		if(y&1)res = (res * x) % MOD;
		y = y>>1;
		x = (x * x) % MOD;
	}
	return res;
}

void solve(){
	int n;
	cin >> n;
	int a[n];
	int sum = 0;
	for(int i = 0; i < n; ++i){
		cin >> a[i];
		sum += a[i];
	}
	sum %= MOD;
	sum = (sum * sum) % MOD;
	int in = 0;
	for(int i = 0; i < n; ++i){
		in += (a[i] * a[i]) % MOD;
		in %= MOD;
	}
	sum -= in;
	sum = (sum + MOD) % MOD;
	int ans = (sum * powmod(2, MOD - 2)) % MOD;
	cout << ans << endl;
}

int32_t main(){
	IO;
	
	int nT = 1;
	//cin >> nT;
	for(int i = 1; i <= nT; ++i)
		solve();
	return 0;
}


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

typedef long long ll;
typedef pair<int,int> pii;

long long MOD = 10000000000 + 7;

int main(){
  cout << setprecision(10);
  string S; cin >> S;

  int ans = 0;
  for(char c: S){
    int num = c - '0';
    ans += num;
    ans %= 9;
  }
  cout << (ans%9==0 ? "Yes" : "No") << endl;
}


Measured memory_bytes: 3720
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long 
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(),(x).end()
#define forn(i, a, b) for (int i=a; i<(signed)(b); ++i)
#define pb push_back
 
 
// debug templates 
#define debug(x)       cerr<< #x <<" : "<< x << endl;
#define debuga(A,N)    cerr<< #A <<" : [";for(int i = 0; i<N;i++) cerr<<A[i]<<" "; cerr<<"]\n";
#define debuga2(A,N,M) cerr<< #A << " : \n"; for(int i=0;i<N;i++){cerr<<"[";for(int j=0;j<M;++j) cerr<<A[i][j]<<" ";cerr<<"]\n";}
#define debugp(p)      cerr<< #p <<" : "<<"("<<(p).first<<","<<(p).second<<")\n";
#define debugv(v)      cerr<< #v <<" : "<<"[";for(int i = 0; i< (v).size(); i++) cerr<<v[i]<<" "; cerr<<"]\n";
#define debugv2(v)     cerr<< #v << " : \n"; for(int i=0;i<v.size();i++){cerr<<"[";for(int j=0;j<(v[0].size());++j) cerr<<v[i][j]<<" ";cerr<<"]\n";}
#define debugs(m)      cerr<< #m <<" : [ "; for(auto itr = m.begin(); itr!=m.end();itr++) cerr<<*itr<<" "; cerr<<"]\n";
#define debugm(m)      cerr<< #m <<" : [ "; for(auto itr = m.begin();itr!=m.end(); itr++) cerr<<"("<<itr->first<<","<<itr->second<<") ";cerr<<"]\n";
int h,w,k;
char c[7][7], temp[7][7];

void reset_temp(){
	forn(i,0,h) forn(j,0,w) temp[i][j] = c[i][j];
}

void color(int i, int j){
	forn(x,0,h){
		// color that row
		if(i & (1<<x)){
			forn(y,0,w) temp[x][y] = '.';
		}
	}
	forn(y,0,w){
		if(j & (1<<y)){
			forn(x,0,h) temp[x][y] = '.';
		}
	}
}

int count(){
	int ans = 0;
	forn(i,0,h) forn(j,0,w) if(temp[i][j] == '#') ++ans;
	return ans;
}

void solve(){
	cin >> h >> w >> k;
	int ans = 0;
	forn(i,0,h) forn(j,0,w) cin >> c[i][j];
	forn(i,0,(1<<h)){
		forn(j,0,(1<<w)){
			reset_temp();
			color(i,j);
			if(count() == k) ++ans;
		}
	}
	cout << ans;
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	solve();
	return 0;
}
 


Measured memory_bytes: 3656
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<sstream>
#include<vector>
#include<ctime>
#include<unordered_map>
using namespace std;
typedef long long ll;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int inf=0x3f3f3f3f;
const int maxn=2e6;
ll cmp(ll a,ll b)
{
	return a>b;
}
ll h[maxn];
int main()
{
	IOS;
	ll n,k;
	cin>>n>>k;
	for(ll i=0;i<n;i++)
	{
		cin>>h[i];
	}
	sort(h,h+n,cmp);
	ll sum=0;
	for(ll i=k;i<n;i++)
	{
		sum+=h[i];
	}
	cout<<sum<<endl;
	return 0;
}


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

using namespace std;

int main()
{
    int x, n;
    cin >> x >> n;

    set<int> p;

    for (int i = 1; i <= n; i++)
    {
        int num;
        cin >> num;
        p.insert(num);
    }

    int num = x;
    int i = 0;    
    int result;

    while(true)
    {
        result = num - i;
        auto itr = p.find(result);
        if(itr == p.end()) break;

        result = num + i;
        itr = p.find(result);
        if(itr == p.end()) break;

        i++;
    }

    cout << result << endl;

    return 0;
}

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

using namespace std;

int main(void) {
  
  long long X;
  cin >> X;

  for (long long a = -10000; a < 10000; a++) {
    for (long long b = -10000; b < a; b++) {
      if ( a*a*a*a*a - b*b*b*b*b == X ) {
        cout << a << ' ' << b << endl;
        return 0;
      }
    }
  }

}


Measured memory_bytes: 3636
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def division_with_round_up(x, y):
    return -(-x // y)


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    B = [int(x) for x in input().split()]

    acnt = 0
    bcnt = 0

    for i in range(N):
        if A[i] == B[i]:
            continue
        elif A[i] > B[i]:
            bcnt += A[i] - B[i]
        else:
            acnt += division_with_round_up(B[i] - A[i], 2)
            bcnt += (B[i] - A[i]) % 2

    if acnt < bcnt:
        print("No")
    else:
        print("Yes")


if __name__ == '__main__':
    main()


Measured memory_bytes: 10548
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>

using namespace std;

int main() {
    int m=0;
    string S;
    cin >> S;
    if (S[0] != 'A') {
		cout << "WA";
        return 0 ;
    }
    S.erase(0,1);
    for (int j = 1; j <S.size()-1 ; ++j) {
        if(S[j]=='C'){
            m++;
            S.erase(j,1);
            j--;
        } 
    }
	 if (m!=1){
            cout<<"WA";
            return 0;
        }
    for (int i = 0; i <S.size() ; ++i) {
        if(S[i]>=97){
            continue;
        }else{
            cout<<"WA";
            return 0;
        }
    }cout<<"AC";


}

Measured memory_bytes: 256
#include <stdio.h>

#define MAX 100
#define WHITE 0
#define GRAY 1
#define BRACK 2
#define INF (1<<21)

int main(){
  int n, num, i, j, u, v, min_v, ans=0;
  int array[MAX][MAX], d[MAX], p[MAX], road_color[MAX];

  scanf("%d", &n);

  for( i=0; i<n; i++){
    for( j=0; j<n; j++){
      scanf("%d", &num);
      array[i][j] = ( num == -1 ) ? INF : num;
    }
  }

  for( i=0; i<n; i++){
    d[i] = INF;
    p[i] = -1;
    road_color[i] = WHITE;
  }

  d[0] = 0;

  while(1){
    min_v = INF;
    u = -1;

    for( i=0; i<n; i++){
      if( min_v > d[i] && road_color[i] != BRACK ){
	u = i;
	min_v = d[i];
      }
    }
      if( u == -1 )break;

      road_color[u] = BRACK;

      for( v=0; v<n; v++){
	if( road_color[v] != BRACK && array[u][v] != INF ){
	  if( d[v] > array[u][v] ){
	    d[v] = array[u][v];
	    p[v] = u;
	    road_color[v] = GRAY;
	  }
	}
      }
    }

  for( i=0; i<n; i++){
    if( p[i] != -1 ) ans += array[i][p[i]];
  }

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

  return 0;
}

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

#define FI(i,a,b) for(int i=(a);i<=(b);i++)
#define FD(i,a,b) for(int i=(a);i>=(b);i--)

#define LL long long
#define Ldouble long double
#define PI 3.14159265358979323846264338327950288419

#define PII pair<int,int>
#define PLL pair<LL,LL>
#define mp make_pair
#define fi first
#define se second

using namespace std;

int n, s[2002], mini[2002][2002], x;
LL ans = 1LL << 60;

int slime(int id){
	while(id <= 0) id += n;
	return id;
}

int main(){
	scanf("%d %d", &n, &x);
	FI(i, 1, n) scanf("%d", &s[i]);
	FI(i, 1, n) mini[i][0] = s[i];
	FI(i, 1, n){
		FI(j, 1, n){
			mini[j][i] = min(mini[j][i - 1], s[slime(j - i)]);
		}
	}
	//enumerate how many times x-spell can be used
	FI(i, 0, n){
		LL temp = 0;
		FI(j, 1, n) temp += mini[j][i];
		ans = min(ans, temp + 1LL * i * x);
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 16000
import java.io._
import java.util.StringTokenizer

import scala.collection.mutable
import scala.util.Sorting
import math.{abs, max, min}
import scala.collection.mutable.{ArrayBuffer, ListBuffer}
import scala.reflect.ClassTag

object Main {
  val MOD = 1000000007
  val out = new PrintWriter(System.out)

  def solve(): Unit = {
    val sc = new InputReader(System.in)
    val R = sc.nextInt()

    val ans = if (R < 1200) "ABC"
    else if (R < 2800) "ARC"
    else "AGC"

    out.println(ans)
  }

  def main(args: Array[String]): Unit = {
    solve()
    out.flush()
  }


  class InputReader(val stream: InputStream) {
    private val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    private var tokenizer: StringTokenizer = _

    def next(): String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = next().toInt
    def nextLong(): Long = next().toLong
    def nextChar(): Char = next().charAt(0)
  }
  def rep(n: Int)(f: Int => Unit): Unit = {
    var i = 0
    while(i < n) { f(i); i += 1 }
  }
  def rep_r(n: Int)(f: Int => Unit): Unit = {
    var i = n - 1
    while(i >= 0) { f(i); i -= 1 }
  }

  def map[@specialized A: ClassTag](n: Int)(f: Int => A): Array[A] = {
    val res = Array.ofDim[A](n)
    rep(n)(i => res(i) = f(i))
    res
  }

  implicit class ArrayOpts[A](val as: Array[A]) extends AnyVal {
    // todo Orderingだとboxing発生するので自作Orderを用意したい
    def maxByOpt[B: Ordering](f: A => B): Option[A] = {
      if (as.nonEmpty) Some(as.maxBy(f)) else None
    }

    def grpBy[K](f: A => K): mutable.Map[K, ArrayBuffer[A]] = {
      val map = mutable.Map.empty[K, ArrayBuffer[A]]
      rep(as.length)(i => map.getOrElseUpdate(f(as(i)), ArrayBuffer()) += as(i))
      map
    }

    def sumBy[B](f: A => B)(implicit num: Numeric[B]): B = {
      var sum = num.zero
      rep(as.length)(i => sum = num.plus(sum, f(as(i))))
      sum
    }

    def minByEx[B](f: A => B, ixRange: Range = as.indices)(implicit cmp: Ordering[B]): (A, B) = {
      limit(f, ixRange)(cmp.lt)
    }

    def maxByEx[B](f: A => B, ixRange: Range = as.indices)(implicit cmp: Ordering[B]): (A, B) = {
      limit(f, ixRange)(cmp.gt)
    }

    private def limit[B](f: A => B, ixRange: Range)(cmp: (B, B) => Boolean): (A, B) = {
      var limA = as(ixRange.head)
      var limB = f(limA)

      for (i <- ixRange.tail) {
        val a = as(i)
        val b = f(a)
        if (cmp(b, limB)) {
          limA = a
          limB = b
        }
      }
      (limA, limB)
    }
  }

  implicit class IterableOpts[A](val as: Iterable[A]) extends AnyVal {
    def sumBy[B](f: A => B)(implicit num: Numeric[B]): B = {
      as.foldLeft(num.zero)((acc, a) => num.plus(acc, f(a)))
    }
  }
}


Measured memory_bytes: 25424
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define rep(i, n) for(i = 0; i < (n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define MOD 1000000007
#define INF 1 << 30

using namespace std;
typedef long long ll;
typedef pair<int, int> pp;

int main(void) {
	int num, i, j, ans = INF, sum;
	cin >> num;
	vector<int> d(num);
	rep(i, num)
		cin >> d[i];
	rep(i, 101) {
		sum = 0;
		rep(j, num) {
			sum += (d[j] - i) * (d[j] - i);
		}
		chmin(ans, sum);
	}
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  
 int n,k; cin>>n>>k;
 bool arr[n]{};
  for(int i = 0 ; i<k ; i++){
    int di; cin>>di;
    for(int j = 0 ; j<di ; j++){
      int x; cin>>x;
      arr[x-1]=true;
    }
    
  }
  int cnt = 0 ; 
  for(int i = 0 ; i<n ; i++)if(!arr[i])cnt++;
  
  cout<<cnt;
  
 return 0; 
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
  ll n;
  cin >> n;
  ll a[2][n];
  for(ll i=0;i<2;i++){
    for(ll j=0;j<n;j++){
        cin >>a[i][j];
    }
  }
  ll ans=0;
  for(ll i=0;i<n;i++){
    ll sum=0;
    for(ll j=0;j<=i;j++){
      sum+=a[0][j];
    }
    for(ll j=i;j<n;j++){
       sum+=a[1][j];
    }
    ans=max(ans,sum);
  }
  cout <<ans<<endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace AtCoder
{
	public class Program
	{
		static void Main(string[] args)
		{
			int N = Int32.Parse(Console.ReadLine());
			decimal[] a = Console.ReadLine().Split().Select(p => decimal.Parse(p)).ToArray();

			decimal bumbo = 0M;
			for(int i=0; i<N; i++)
			{
			//	Console.WriteLine(bumbo + " " + (1/a[i])) ;
					bumbo += 1/a[i];
			}

			decimal ans = 1/bumbo;
			Console.WriteLine(ans + "");
		}
	}
}


Measured memory_bytes: 13396
def main():
    n, k = map(int, input().split())
    r, s, p = map(int, input().split())
    ts = list(input())

    hands = {"r": p, "s": r, "p": s}
    ans = 0
    skip = [0]*n
    for i in range(n):
        if skip[i] == 1:
            continue

        if i+k > n-1:
            ans += hands[ts[i]]

        else:
            if ts[i] != ts[i+k]:
                ans += hands[ts[i]]
            else:
                ans += hands[ts[i]]
                skip[i+k] = 1

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 4792
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long int;
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; }
const ll INF = 1e9;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
ll sum(string s){
    s += "+";
    ll index = 0,res = 0;
    string t = "";
    while(index < s.length()){
        if (s[index] != '+'){
            t += s[index];
        }
        else{
            rep(i,t.length()){
                res += (t[i]-'0')*pow(10,t.length()-i-1);
            }
            t = "";
        }
        index++;
    }
    return res;
}
int main(){
    string s,u;
    cin >> s;
    ll ans = 0;
    rep(i,(1<<s.length()-1)){
        u = "";
        rep(j,s.length()-1){
            u += s[j];
            if (i&(1<<j)) u += "+";
        }
        u += s[s.length()-1];
        ans += sum(u);
    }
    PRINT(ans);
}

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


void solve(){
    string s,t;
    cin >> s >> t;
    int n = t.size();
    string ans = "No";
    rep(i,n){
        t = t[n-1] + t.substr(0, n-1);
        //cout << t << endl;
        if(s==t) ans = "Yes";
    }
    cout << ans << endl;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 1000001;

int n, cnt[N];
vector <int> a;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    a.resize(n);
    for(auto &i : a) cin >> i;
    map <int, int> f;
    for(auto &i : a){
        f[i]++;
        if(f[i] >= 3) continue;
        for(int j = i ; j < N ; j += i){
            cnt[j]++;
        }
    }
    int ans = 0;
    for(auto &i : a){
        if(cnt[i] == 1) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 17152
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=1000;
int n,m;
typedef long long ll;
struct CAKE
{
	ll A,B,C;
}cak[MAXN+5];
int i,j,k;
bool cmp(CAKE a,CAKE b)
{
	return a.A*i+a.B*j+a.C*k>b.A*i+b.B*j+b.C*k;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld%lld",&cak[i].A,&cak[i].B,&cak[i].C);
	ll ans=0;
	for(i=-1;i<=1;i+=2)
		for(j=-1;j<=1;j+=2)
			for(k=-1;k<=1;k+=2)
			{
				sort(cak+1,cak+n+1,cmp);
				ll tot[3]={};
				for(int p=1;p<=m;p++)
					tot[0]+=cak[p].A,tot[1]+=cak[p].B,tot[2]+=cak[p].C;
				ans=max(ans,tot[0]*i+tot[1]*j+tot[2]*k);
			}
	printf("%lld\n",ans);
	return 0;
}
//fantastic atcoder! wonderful ABC!!!


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
using namespace std;
int n,k;
bool notuse[20]={0};
char s[20];
int main()
{
	cin>>n>>k;
	for(int i=1;i<=k;i++)
	{
		int u;
		cin>>u;
		notuse[u]=1;
	}
	for(int i=n;i<1e5;i++)
	{
		sprintf(s,"%d",i);
		bool ok=true;
		for(char* t=s;*t;t++)
		{
			if(notuse[*t-'0'])
				ok=false;
		}
		if(ok)
		{
			cout<<i<<endl;
			break;
		}
	}	
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int a[4][3][10] = {0};
	int n, i;
	int bl, fl, ro;

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		int b, f, r, v;
		scanf("%d %d %d %d", &b, &f, &r, &v);
		a[b - 1][f - 1][r - 1] += v;
	}

	for (bl = 1; bl < 5; bl++) {
		for ( fl = 1; fl < 4; fl++) {
			for ( ro = 1; ro < 11; ro++)
				printf(" %d", a[bl - 1][fl - 1][ro - 1]);
			putchar('\n');
		}
		if (bl < 4)
			printf("####################\n");
	}
	
    return 0;
}

Measured memory_bytes: 612
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
using namespace std;

int main() {
	int H, W,C;
	cin >> H >> W >> C;
	if (W/H >= C) {
		cout << C << endl;
	}

	else {
		cout << W / H << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include<math.h>
using namespace std;
#define MAX 100005
#define ALPHA 26
char S[MAX];
int main()
{
    double A,B,H,M,pi=acos(-1);
    scanf("%lf %lf %lf %lf",&A,&B,&H,&M);
    double minute_angle=M*pi/30;
    double hour_angle=(H*60+M)*pi/(6*60);
    double diff;
    if(hour_angle>=minute_angle) diff=hour_angle-minute_angle;
    else diff=minute_angle-hour_angle;
    if(diff>pi) diff=pi*2-diff;
    double ans=sqrt(A*A+B*B-2*A*B*cos(diff));
    printf("%.10f",ans);
    return 0;
}


Measured memory_bytes: 4252
#include<stdio.h>
#include<string.h>
int main(){
  char s[200001];
  scanf("%s",s);
  int n=strlen(s);
  int a=0, z=0;
  for(int i=0; i<n; i++){
    if(s[i]=='A'){
      a=i;
      break;
    }
  }
  for(int j=n-1; j>=0; j--){
    if(s[j]=='Z'){
      z=j;
      break;
    }
  }
  printf("%d\n",z-a+1);
  return 0;
}


Measured memory_bytes: 384
#include<cstdio>
using namespace std;
typedef long long ll;
ll n,m;
ll c1(ll p){return p/2;}
ll c2(ll p){return (p+1)/2;}
int main()
{
	scanf("%lld%lld",&n,&m);
	if(n==1||m==1)
	{
		printf("1\n");
		return 0;
	}
	printf("%lld\n",c1(n)*c1(m)+c2(n)*c2(m));
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define ppi pair< pair<int,int>,int >
#define bs binary_search
#define gcd _gcd
#define fs first
#define sc second
#define MOD 1000000007
int ABS(int a){return max(a,-a);}
ll ABS(ll a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
int gif(int x,int a){return (x%a==0)?(x/a):((x/a)+1);}
ll gif(ll x,ll a){return (x%a==0LL)?(x/a):((x/a)+1LL);}
int lif(int x,int a){return (x/a);}
ll lif(ll x,ll a){return (x/a);}

const int N = 100005;
int a[N];
int dp[N];

void solve()
{
    int n;
    cin>>n;

    for(int i=1;i<=n;i++)
        cin>>a[i];

    dp[1]=0;
    dp[2] = ABS(a[2]-a[1]);

    for(int i=3;i<=n;i++)
    {
        dp[i] = min(dp[i-1]+ABS(a[i]-a[i-1]),dp[i-2]+ABS(a[i]-a[i-2]));
    }

    cout<<dp[n]<<"\n";
}

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

    ios::sync_with_stdio(0);
    cin.tie(0);

    solve();

}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
//#include <chrono>
#pragma GCC optimize("Ofast")
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
typedef pair<ll, ll> P;
const ll INF = (1LL<<60);

void dfs1(int n, mat &G, vec &ord){
    int k(0);
    vector<int> iter(n, -1);
    stack<int> sta;
    rep(i, n) {
        if(iter[i] < 0) sta.push(i);
        while (!sta.empty()) {
            int v = sta.top();
            if ((++iter[v]) == G[v].size()) {
                ord[k++] = v;
                sta.pop();
            } else {
                int to = G[v][iter[v]];
                if(iter[to] < 0) sta.push(to);
            }
        }
    }
}
void dfs2(int n, mat &G, vec &ord, mat &res){
    int k(0);
    vector<bool> used(n, false);
    stack<int> sta;
    Rrep(i, n){
        int s = ord[i];
        if(!used[s]){
            used[s] = true;
            sta.push(s);
            while(!sta.empty()){
                int v = sta.top(); sta.pop();
                res[k].push_back(v);
                for(int to : G[v]) {
                    if(!used[to]) {
                        used[to] = true;
                        sta.push(to);
                    }
                }
            }
            ++k;
        }
    }
    res.resize(k);
}

void scc(mat &G, mat &res){
    int n = G.size();
    mat G_rev(n, vec(0));
    rep(u, n) for(int v : G[u]) G_rev[v].push_back(u);
    vec ord(n);
    dfs1(n, G, ord);
    dfs2(n, G_rev, ord, res);
}

void input(mat &G){
    rep(i,M){
        int a, b;
        scanf("%d%d", &a, &b);
        G[a].push_back(b);
    }
}

void output(mat &scc_list){
    printf("%d\n", (int)scc_list.size());
    for(vec v : scc_list){
        int n = v.size();
        printf("%d ", n);
        rep(i, n) printf("%lld%c", v[i], " \n"[i == n - 1]);
    }
}
int main() {
    cin >> N >> M;
    mat G(N, vec(0)), scc_list(N, vec(0));
    input(G);
    scc(G, scc_list);
    output(scc_list);
}



Measured memory_bytes: 79204
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N = int(input())
bt,bx,by = 0,0,0
for i in range(N):
    t,x,y = inpl()
    dt = t-bt
    dx,dy = abs(x-bx),abs(y-by)
    if dx+dy > dt:
        print('No')
        exit()
    else:
        if (dt - (dx+dy)) %2 != 0:
            print('No')
            exit()
    bt,bx,by = t,x,y

print('Yes')


Measured memory_bytes: 4212
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
using namespace std;
typedef long long LL;
LL gi () {
    LL ret=0; char ch=getchar();
    while((ch<'0' || ch>'9') && ch!='-') ch=getchar();
    char c=ch=='-'?getchar():ch;
    while(c>='0' && c<='9') ret=ret*10+c-'0',c=getchar();
    return ch=='-'?-ret:ret;
}
map<int,int> a;
int n;
int main () {
    n = gi();
    for(int i=1;i<=n;i+=1) {
        a[gi()] += 1;
    }
    int ans = 0;
    for(map<int,int> ::iterator it = a.begin();it != a.end();it++) {
        if(it->first > it->second) ans += it->second;
        else if(it->first < it->second) ans += it->second - it->first;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 4736
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


//B
template<typename T>
struct BIT{//1_Indexed
  int n;
  vector<T> bit;
  BIT(int n_):n(n_+1),bit(n,0){}

  T sum(int a){
  int ret = 0;
  for(int i = a; i > 0; i -= i & -i) ret += bit[i];
  return ret;
  }

  void add(int a,int w){
    for(int i = a; i <= n; i += i & -i)bit[i] += w;
  }

  T query(int l,int r){
    return sum(l-1)-sum(r-1);
  }

};
//E
int main(){
  long long n,m;cin>>n>>m;
  vector<long long> a(n);
  for(int i = 0; n > i; i++){
    cin>>a[i];
    a[i] -= m;
  }
  vector<long long> b(n+1);
  vector<long long> c(n+1);
  b[0] = 0;
  c[0] = 0;
  for(int i = 1; n >= i; i++){
    b[i] = b[i-1]+a[i-1];
    c[i] = b[i];
  }
  sort(c.begin(),c.end());
  c.erase(unique(c.begin(),c.end()),c.end());
  vector<long long> d(c.size());
  for(int i = 0; n >= i; i++){
    auto z = lower_bound(c.begin(),c.end(),b[i]) - c.begin();
    d[z]++;
  }
  BIT<int> e(c.size());
  for(int i = 1; c.size() >= i; i++){
    e.add(i,d[i-1]);
  }
  long long ans = 0;
  for(int i = 0; n >= i; i++){
    
    auto z = lower_bound(c.begin(),c.end(),b[i]) - c.begin();
    ans += max(0,e.sum(c.size())-e.sum(z)-1);
    //cout <<sum(z) << endl;
    //cout <<":" << b[i] << " " << z << endl;
    e.add(z+1,-1);
  }
  cout << ans << endl;

}

Measured memory_bytes: 7296
#include <stdio.h>
#include <stdlib.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define MAXN 8

int Perm[MAXN + 1];
int InitGenPerm = 0;

int cmpint(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int cmp(const void *a, const void *b)
{
    return cmpint((const int *)a, (const int *)b);
}

int GenPerm(int n)
{
    static int i[MAXN + 1];
    int j, k, flag;

    if (n > MAXN)
        return (InitGenPerm = 0);
    if (InitGenPerm)
    {
        for (k = n; i[k] == n; k--)
            ;
        i[k]++;
    }
    else
        i[k = 1] = 1;

    while (k > 0)
    {
        while (1)
        {
            Perm[k] = i[k];
            for (flag = 0, j = 1; j < k; j++)
                if (Perm[k] == Perm[j])
                    flag = 1;
            if (flag)
                break;
            else if (k == n)
                return (InitGenPerm = 1);
            else
                i[++k] = 1;
        }
        for (; i[k] == n; k--)
            ;
        i[k]++;
    }
    return (InitGenPerm = 0);
}

int main(void)
{
    int ans[2];

    int n;
    scanf("%d", &n);

    int pq[2][n];
    rep(i, 2)
        rep(j, n)
            scanf("%d", &pq[i][j]);

    int flag = 1;
    rep(i, n)
    {
        if (pq[0][i] != pq[1][i])
            flag = 0;
    }
    if (flag)
    {
        puts("0");
        return 0;
    }

    qsort(pq, 2, sizeof *pq, cmp);

    int cnt = 0;
    int j = 0;
    while (GenPerm(n))
    {
        int flag = 1;
        ++cnt;
        for (int i = 1; i <= n; i++)
            if (Perm[i] != pq[j][i - 1])
                flag = 0;
        if (flag)
        {
            ans[j] = cnt;
            //printf("cnt:%d\n", ans[j]);
            j++;
        }
    }

    printf("%d\n", abs(ans[0] - ans[1]));

    return 0;
}

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

using namespace std;

const int N = 2e5 + 5;
long long n, bit[N], h[N], a[N], ans, dp[N];

void update(int id, long long val){
	for(;id <= n; id |= (id + 1))
		bit[id] = max(bit[id], val);
}

long long query(int id){
	long long res = 0;
	for(; id >= 0;id = (id & (id + 1)) - 1)
		res = max(res, bit[id]);
	return res;
}

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

	cin>>n;
	for(int i=1;i<=n;++i)cin>>h[i];
	for(int i=1;i<=n;++i)cin>>a[i];

	for(int i=1;i<=n;++i){
		dp[i] = query(h[i] - 1) + a[i];
		update(h[i], dp[i]);
		ans = max(ans, dp[i]);
	}
	cout<<ans<<"\n";

	return 0;
}

Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back
#define mp make_pair
#define pii pair<ll,ll>
#define vi vector<ll>
#define vs vector<string>
#define vii vector<pii>
#define mi map<ll,ll>
#define mii map<pii,ll>
#define mc map<char,ll>
#define itr ::iterator
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fe(i,a,b) for(ll i=a;i<=b;i++)
#define fn(i,a,b) for(ll i=a;i>b;i--)
#define fne(i,a,b) for(ll i=a;i>=b;i--)
#define fm(it,m) for(it = m.begin();it != m.end();++it)
#define all(v) v.begin(),v.end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define M 1000000007
#define pi 3.14159265358979323846
int dp[100005][3] = {0};
int a[100005][3];

int main()
{  
   #ifndef ONLINE_JUDGE
   freopen("input.txt","r",stdin);
   freopen("output.txt","w",stdout);
   #endif
   IOS;
   
   // int T=1;
   // cin>>T;
   // f(t,0,T)
   //  { 
      ll n=0,i=0,j=0,k=0,ans=INT_MIN;
      cin>>n;
      
      f(i,0,n)
       cin>>a[i][0]>>a[i][1]>>a[i][2];

      dp[0][0] = a[0][0];
      dp[0][1] = a[0][1];
      dp[0][2] = a[0][2];

      f(i,0,n-1)
       { 
         f(j,0,3)
          {
            dp[i+1][(j+1)%3] = max(dp[i+1][(j+1)%3],dp[i][j] + a[i+1][(j+1)%3]);
            dp[i+1][(j+2)%3] = max(dp[i+1][(j+2)%3],dp[i][j] + a[i+1][(j+2)%3]);

            // ans = max(ans,dp[i+1][(j+1)%3]);
            // ans = max(ans,dp[i+1][(j+2)%3]);
          }
       }

      ans = max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));

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


Measured memory_bytes: 5996
s = input()
ACGT = "ACGT"
#s = "SHINJUKU"

def isACGT(c):
    if (c in ACGT):
        return True
    else:
        return False

count = 0
max = 0
for i in range(len(s)):
    if (isACGT(s[i])):
        count = count + 1
    else:
        max = count if max < count else max
        count = 0
max = count if max < count else max
print(max)

Measured memory_bytes: 3064